黑马程序员技术交流社区

标题: 求大师解决：代码设计方程式：a^3 + b^3 = c^3 + d^3 [打印本页]
作者: 王小丑    时间: 2013-2-2 19:08
标题: 求大师解决：代码设计方程式：a^3 + b^3 = c^3 + d^3
本帖最后由 张向辉 于 2013-2-5 12:37 编辑

题目要求如下：
方程式：a^3 + b^3 = c^3 + d^3
其中：“^”表示乘方。a、b、c、d是互不相同的小于30的正整数。
这个方程有很多解。比如：
a = 1，b=12，c=9，d=10 就是一个解。因为：1的立方加12的立方等于1729，而9的立方加10的立方也等于1729。
当然，a=12，b=1，c=9，d=10 显然也是解。
如果不计abcd交换次序的情况，这算同一个解。
你的任务是：找到所有小于30的不同的正整数解。把a b c d按从小到大排列，用逗号分隔，每个解占用1行。比如，刚才的解输出为：
1,9,10,12
不同解间的顺序可以不考虑。
希望给出可运行的程序 焦急等待答案！
作者: 许晓华    时间: 2013-2-2 19:39
本帖最后由 许晓华 于 2013-2-3 07:49 编辑

public class x
{
      public static void f(int[] a, int n)
       {     
              if(n==4)
              {
                     if((a[0]<a[1])&&(a[0]<a[2])&&(a[2]<a[3])&&(a[0]*a[0]*a[0]+a[1]*a[1]*a[1]==a[2]*a[2]*a[2]+a[3]*a[3]*a[3]))
                            System.out.printf("%d,%d,%d,%d\n",a[0],a[2],a[3],a[1]);
                     return;
              }
              for(int i=n; i<a.length; i++)
              {
                     int t = a[n];a[n] = a;a = t;
                     f(a, n+1);
                     t = a[n];a[n] = a;a = t;
              }
       }
       public static void main(String[] args)
       {
              int[] a = new int[30];
              for(int i=0;i<30;i++) a=i+1;
              f(a, 0);
       }
}
楼主是搞软件大赛的？呵呵
这个题目的算法核心是求出N个数中选出M个的排列问题。
即从1~30的30个数中，选出4个来排列。
然后求满足要求的那些排列
用了递归算法。
结果有四种：
1,9,10,12
2,9,15,16
2,18,20,24
10,19,24,27
运行结果截图如下所示：

图片1.png (6.84 KB, 下载次数: 29)

图片1.png
作者: 薛虎    时间: 2013-2-2 20:26
  1. class Temp
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int cup;
  6.                 for(int a=1; a<=30; a++)
  7.                 {
  8.                         for(int b=1; b<=30; b++)
  9.                         {
  10.                                 for(int c=1; c<=30; c++)
  11.                                 {
  12.                                         for(int d=1; d<=30; d++)
  13.                                         {
  14.                                                 if(a*a*a+b*b*b==c*c*c+d*d*d&&a!=b&&b!=c&&c!=d&&d!=a&&a!=c&&b!=d)
  15.                                                 {
  16.                                                         if(a<b) {cup = a; a = b; b = cup;}
  17.                                                         if(a<c) {cup = a; a = c; c = cup;}
  18.                                                         if(a<d) {cup = a; a = d; d = cup;}
  19.                                                         if(b<c) {cup = b; b = c; c = cup;}
  20.                                                         if(b<d) {cup = b; b = d; d = cup;}
  21.                                                         if(c<d) {cup = c; c = d; d = cup;}
  22.                                                         System.out.println(d+","+c+","+b+","+a);
  23.                                                 }
  24.                                         }
  25.                                 }
  26.                         }
  27.                 }
  28.         }
  29. }
复制代码
作者: 许晓华    时间: 2013-2-3 07:44
本帖最后由 许晓华 于 2013-2-3 07:49 编辑
薛虎 发表于 2013-2-2 20:26


哥们，请教，如何在贴代码的时候加制表符，象你这样
作者: 丁强强    时间: 2013-2-3 08:51
本帖最后由 丁强强 于 2013-2-3 08:54 编辑
  1. class xiangmu
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                         chazhao q = new chazhao();
  6.                         q.chazhao();

  8.                 }
  9. }
  10. class chazhao
  11. {
  12.         public void chazhao()
  13.         {
  14.                 for (int a=1;0<a && a<=30 ;a++ )
  15.                 {
  16.                  for (int b=1;0<b && b<=30 ;b++ )
  17.                 {
  18.                  for (int c=1;0<c && c<=30 ;c++ )
  19.                 {
  20.                 for (int d=1;0<d && d<=30 ;d++ )
  21.                 {
  22.                         paixu(a,b,c,d);

  24.                 }
  25.                 }
  26.                 }
  27.                 }
  28.         }
  29.         

  31.                 public void paixu(int a, int b, int c ,int d)
  32.         
  33.                 {
  34.                   if(a*a*a+b*b*b==c*c*c+d*d*d&&a!=b&&b!=c&&c!=d&&d!=a&&a!=c&&b!=d)

  36.                         {
  37.                                 int cup;


  40.                 if(a<b) {cup = a; a = b; b = cup;}

  42.                 if(a<c) {cup = a; a = c; c = cup;}

  44.                 if(a<d) {cup = a; a = d; d = cup;}

  46.                 if(b<c) {cup = b; b = c; c = cup;}

  48.                 if(b<d) {cup = b; b = d; d = cup;}

  50.                 if(c<d) {cup = c; c = d; d = cup;}
  51.               
  52.                           System.out.println(a+","+b+","+c+","+d);
  53.                                   }
  54.         }
  55. }
复制代码
如果不计abcd交换次序的情况，这算同一个解。

这一步为什么我不成立 我引用的@薛虎的排序     
作者: 薛虎    时间: 2013-2-3 10:38
许晓华 发表于 2013-2-3 07:44
哥们，请教，如何在贴代码的时候加制表符，象你这样

源码在editplus里就是有制表符的。
在论坛发帖的时候直接把源码复制过来，粘贴的时候点击论坛编辑框上的那个“<>”，把代码粘帖进去就行了。
作者: 朱玉玺    时间: 2013-2-3 11:19
本帖最后由 朱玉玺 于 2013-2-3 11:25 编辑
许晓华 发表于 2013-2-2 19:39
public class x
{
      public static void f(int[] a, int n)

这个题目的算法核心是求出N个数中选出M个的排列问题。 说的很透彻啊。之前还看了这个帖子
http://bbs.itheima.com/forum.php?mod=viewthread&tid=37306&page=1&extra=#pid223918在n个整数中找到相加之和为t的所有组合
核心也是从N个数选出M个数的问题，其实判断条件好处理，取数这个过程比较麻烦。
作者: 许晓华    时间: 2013-2-3 11:37
薛虎 发表于 2013-2-3 10:38
源码在editplus里就是有制表符的。
在论坛发帖的时候直接把源码复制过来，粘贴的时候点击论坛编辑框上的 ...

嘿嘿，多谢指点
作者: 许晓华    时间: 2013-2-3 11:38
本帖最后由 许晓华 于 2013-2-3 13:23 编辑
朱玉玺 发表于 2013-2-3 11:19 http://bbs.ithe ...


那个题是背包问题，选出多少个不固定。这个题是排列问题，固定选4个数
作者: 朱玉玺    时间: 2013-2-3 12:00
许晓华 发表于 2013-2-3 11:38
那个题是背包问题，选出多少个不固定。这个题是背包问题，固定选4个数

呵呵，本质都是选数，数学中的队列组合问题。这个帖子都是乘以3次方，所以成了选组合的问题；如果是a^2+b^4=C^6+d^7,这就变成了队列问题了，先选出所有的组合，然后每一个组合再排队。现在才知道当年学数学的队列组合是干嘛的，敢情就是为了学编程的时候用啊
作者: 王小丑    时间: 2013-2-3 20:09
许晓华 发表于 2013-2-2 19:39
public class x
{
      public static void f(int[] a, int n)

高手 能想出来这个已经很不错了
作者: 许晓华    时间: 2013-2-3 21:25
王文正 发表于 2013-2-3 20:09
高手 能想出来这个已经很不错了

:P 呵呵谢谢，你这题目哪儿来的啊
作者: 王小丑    时间: 2013-2-3 21:37
许晓华 发表于 2013-2-3 21:25
呵呵谢谢，你这题目哪儿来的啊

国外的一个程序大赛题 呵呵
作者: 王小丑    时间: 2013-2-3 22:06
王文正 发表于 2013-2-3 21:37
国外的一个程序大赛题 呵呵

有兴趣的看看这个实现方式是不是很简单：
public class test08 {
public static void main(String[] args) {
int i,j,k,p;
for(i=1;i<30;i++){
for(j=i+1;j<30;j++){
for(k=j+1;k<30;k++){
for(p=k+1;p<30;p++){
if(i*i*i+j*j*j==k*k*k+p*p*p||i*i*i+k*k*k==j*j*j+p*p*p
||i*i*i+p*p*p==j*j*j+k*k*k){
System.out.println(i+”,”+j+”,”+k+”,”+p);
}
}
}
}
}
}
}
作者: 王小丑    时间: 2013-2-3 22:06
我感觉这样也可以实现 有兴趣的看一下
public class p8 {
public static void main(String[] args) {
for(int a=1;a<30;a++)
for(int b=a;b<30;b++)
for(int c=a;c<30;c++)
for(int d=c;d<30;d++){
double a3=Math.pow(a,3);
double b3=Math.pow(b,3);
double c3=Math.pow(c,3);
double d3=Math.pow(d,3);
if(a3+b3-c3-d3==0 &&a!=b && a!=c && a!=d && b!=c && b!=d &&c!=d)
System.out.println(a+”,”+c+”,”+d+”,”+b);}
}
}
作者: 王小丑    时间: 2013-2-3 22:07
许晓华 发表于 2013-2-2 19:39
public class x
{
      public static void f(int[] a, int n)

你看一下这样实现不是简单点
public class p8 {
public static void main(String[] args) {
for(int a=1;a<30;a++)
for(int b=a;b<30;b++)
for(int c=a;c<30;c++)
for(int d=c;d<30;d++){
double a3=Math.pow(a,3);
double b3=Math.pow(b,3);
double c3=Math.pow(c,3);
double d3=Math.pow(d,3);
if(a3+b3-c3-d3==0 &&a!=b && a!=c && a!=d && b!=c && b!=d &&c!=d)
System.out.println(a+”,”+c+”,”+d+”,”+b);}
}
}
作者: 许晓华    时间: 2013-2-3 23:00
是简单，比赛可以这样写，节省时间。若面试，最好按我的递归方法，否则会遭到面试官的鄙视。
作者: oxf974025918    时间: 2013-6-24 00:37
本帖最后由 oxf974025918 于 2013-6-24 00:38 编辑
王文正 发表于 2013-2-3 22:07
你看一下这样实现不是简单点
public class p8 {
public static void main(String[] args) {

高手如云
作者: oxf974025918    时间: 2013-6-24 00:41
请问高手们，是for循环节省时间还是递归节省时间？可以分析一下吗？
作者: oxf974025918    时间: 2013-6-24 00:42
王文正 发表于 2013-2-3 21:37
国外的一个程序大赛题 呵呵

高手，多出几个给我们菜鸟欣赏欣赏咯。。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2