黑马程序员技术交流社区

标题: 大神,求帮忙呀 [打印本页]

作者: 土菠萝    时间: 2016-5-31 09:13
标题: 大神,求帮忙呀
一个N位的十进制正整数,如果它的每个位上的数字的N次方的和等于这个数本身,则称其为花朵数。
例如:
当N=3时,153就满足条件,因为 1^3 + 5^3 + 3^3 = 153,这样的数字也被称为水仙花数(其中,“^”表示乘方,5^3表示5的3次方,也就是立方)。
当N=4时,1634满足条件,因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。
当N=5时,92727满足条件。
实际上,对N的每个取值,可能有多个数字满足条件。

程序的任务是:求N=21时,所有满足条件的花朵数。注意:这个整数有21位,它的各个位数字的21次方之和正好等于这个数本身。



作者: 936994215    时间: 2016-5-31 09:13
解题主要思想如下:枚举n位数字中0 — 9出现的次数,根据枚举的次数算出一个数,对比这个数中0 — 9出现的次数是否等于枚举的0 — 9出现的次数相等。如果相等,则该数是水仙花数。
这儿有个C语言版的算法思路:
#include<stdio.h>
#include<string.h>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
usingnamespacestd;
#defineDIGIT21//每次就只用改变这里,就可以算出不同位数的水仙花数了。如果要想算出所用的,这里就写最大,然后再在程序里加一层循环就是咯
intCount[10];//Count用来保存枚举是0——9出现的次数,用以和算出来的值各数字出现次数进行对比。
intcnt1,num1[10][DIGIT+1][DIGIT+1];//cnt1是符合条件的个数。num1用来保存0——9分别出现0——DIGIT次对应的答案
charans[10][DIGIT+1];//保存符合条件的答案
//这两个就是为了排序方便一点
vector<string>v;
strings[10];
voiddeal()
{
intcnt[10];//保存算出来的数0——9出现的次数,用以和Count对比看是否满足条件
intno[DIGIT+1];//算出来的数
memset(no,0,sizeof(no));
memset(cnt,0,sizeof(cnt));
for(intk=1;k<10;k++)
{
if(num1[k][Count[k]][DIGIT]!=0)
{
return;
}
for(inti=0;i<DIGIT;i++)
{
no[i]+=num1[k][Count[k]][i];
if(no[i]>9)
{
no[i+1]+=(no[i]/10);
no[i]%=10;
}
}
}
if(no[DIGIT]!=0)
{
return;
}
if(no[DIGIT-1]!=0)
{
intflag=0;
for(intj=0;j<DIGIT;j++)
{
cnt[no[j]]++;
}
for(intj=0;j<10;j++)
{
if(cnt[j]!=Count[j])
{
flag=1;
break;
}
}
if(!flag)
{
ans[cnt1][DIGIT]='\0';
for(intj=0,k=DIGIT-1;j<DIGIT;j++,k--)
{
ans[cnt1][k]=no[j]+'0';
}
s[cnt1]=ans[cnt1];
v.push_back(s[cnt1]);
cnt1++;
}
}
};
intmain()//计算从0——9出现分别0——DIGIT次时的值
{
for(inti=1;i<10;i++)
{
num1[i][1][0]=1;
intindex=0;
for(intj=1;j<=DIGIT;j++)
{
for(intr=0;r<=index;r++)
{
num1[i][1][r]*=i;
}
for(intr=0;r<=index;r++)
{
if(num1[i][1][r]>9)
{
num1[i][1][r+1]+=(num1[i][1][r]/10);
num1[i][1][r]%=10;
}
}
while(index<DIGIT-1&&num1[i][1][index+1]>0)
{
index++;
if(num1[i][1][index]>9)
{
num1[i][1][index+1]+=(num1[i][1][index]/10);
num1[i][1][index]%=10;
}
}
}
for(intj=2;j<=DIGIT;j++)
{
for(intr=0;r<=DIGIT;r++)
{
num1[i][j][r]=num1[i][1][r]*j;
}
for(intr=0;r<DIGIT;r++)
{
if(num1[i][j][r]>9)
{
num1[i][j][r+1]+=(num1[i][j][r]/10);
num1[i][j][r]%=10;
}
}
}
}//枚举0——9分别出现0——DIGIT次的情况,0——9分别对应a——j
for(inta=0;a<=DIGIT;a++)
{
Count[0]=a;
for(intb=0;b<=DIGIT;b++)
{
if(a+b>DIGIT)//保证出现的次数不大于DIGIT,下同
{
break;
}
Count[1]=b;
for(intc=0;c<=DIGIT;c++)
{
if(a+b+c>DIGIT)
{
break;
}
Count[2]=c;
for(intd=0;d<=DIGIT;d++)
{
if(a+b+c+d>DIGIT)
{
break;
}
Count[3]=d;
for(inte=0;e<=DIGIT;e++)
{
if(a+b+c+d+e>DIGIT)
{
break;
}
Count[4]=e;
for(intf=0;f<=DIGIT;f++)
{
if(a+b+c+d+e+f>DIGIT)
{
break;
}
Count[5]=f;
for(intg=0;g<=DIGIT;g++)
{
if(a+b+c+d+e+f+g>DIGIT)
{
break;
}
Count[6]=g;
for(inth=0;h<=DIGIT;h++)
{
if(a+b+c+d+e+f+g+h>DIGIT)
{
break;
}
Count[7]=h;
for(inti=0;i<=DIGIT;i++)
{
if(a+b+c+e+f+g+h+i>DIGIT)
{
break;
}
Count[8]=i;
intj=DIGIT-a-b-c-d-e-f-g-h-i;
if(j<0)
{
break;
}
Count[9]=j;
deal();
}
}
}
}
}
}
}
}
}//排序,将答案从小到大输出
sort(v.begin(),v.end());
for(inti=0;i<v.size();i++)
{
cout<<v[i]<<endl;
}
return0;
}

为了赚技术分,谅解下。有不懂的再来问。
作者: yu2323637    时间: 2016-5-31 22:13
明天学数组,目前还解决不了你的问题,最主要的是不知道怎么定义21位的整型数。。
作者: fanhongwei1105    时间: 2016-6-1 00:03
package dome;  import java.math.BigInteger;  import java.util.Hashtable;  public class Demo2{         /*          * 本题的思路                   1关键是去掉所含0-9数字个数雷同的21位数以免反复运算增长时候                          比 如123456789012345678901与987654321098765432101与987654321012345678901中的所含数字的个数都是雷同的                          所以其每一位的21次方的和都相等将所得的21次方和 从大到小进行排序若对应的数与原数不相等则都不成立是以若不去掉反复的数将会增长运算时候                                   2认为要将每一位数的21次方之和从大到小排序所以运算从21个9这个最大数开端向下运算又因为10个9的21次方之和跨越了21位数所以从9个912个8开端一次往下运                         算即可如许又可以节俭一项目组时候。           *           * */          private static final int SIZE = 21;          private int[] countArray = new int[10]; // 个数列表          private int[] countSumArray = new int[10]; // 个数总数          private BigInteger[] sumArray = new BigInteger[10];// 值总数          private int offset = 0; // 浮标          /**          *           * 设置当前浮标对应的个数个数的总数值总数          *           *           *           * @param num          *           *            个数          */          private void setValue(int num){                 countArray[offset] = num;                                  if (offset == 0){                                                  countSumArray[offset] = num;                                                  sumArray[offset] = p(9 - offset).multiply(n(num));                                          } else{                          countSumArray[offset] = countSumArray[offset - 1] + num;                          sumArray[offset] = sumArray[offset - 1].add(p(9 - offset).multiply(                          n(num)));                  }          }          /**          *           * 检验当前数据是否匹配          *           *           *           * @return          */          private boolean checkPersentArray(){                  BigInteger minVal = sumArray[offset];// 当前已存在值                  BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(                  n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值                  // 最小值匹配                  if (minVal.compareTo(MAX) > 0){                          return false;                 }                  // 最大值匹配                  if (maxVal.compareTo(MIN) < 0){                          return false;                 }                  String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN                  .toString();                  String maxStr = maxVal.compareTo(MAX) < 0 ? maxVal.toString() : MAX                  .toString();                  // 找到最小值与最大值间首部相同的部分                  int[] sameCountArray = new int[10];                  for (int i = 0; i < SIZE; i++){                          char c;                          if ((c = minStr.charAt(i)) == maxStr.charAt(i)){                                                                  sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;                          } else{                                  break;                         }                  }                  // 判断如果相同部分有数据大于现在已记录的位数返回false                  for (int i = 0; i <= offset; i++){                          if (countArray[i] < sameCountArray[9 - i]){                                  return false;                         }                  }                  // 如果当前值的总数为SIZE位那么判断该值是不是需要查找的值                  if (countSumArray[offset] == SIZE){                          String sumStr = sumArray[offset].toString();                          BigInteger sum = ZERO;                          for (int i = 0; i < sumStr.length(); i++){                                  sum = sum.add(p(sumStr.charAt(i) - '0'));                         }                          return sum.compareTo(sumArray[offset]) == 0;                 }                 return true;         }          /**          *           * 退出循环打印          *           *           *           * @return          */          private void success(){                  System.out.println(SIZE + "位的花朵数为:" + sumArray[offset]);          }          /**          *           * 将浮标指向下一位数          *           *           *           * @return          */          private void next() {                  offset++;                  setValue(SIZE - countSumArray[offset - 1]);          }          /**          *           *           *           * 回退浮标找到最近的浮标并减一          *           *           *           * @return          */          private boolean back(){                  // 回退浮标找到最近的浮标并减一                  if (countArray[offset] == 0){                          while (countArray[offset] == 0){                                  if (offset > 0){                                          offset--;                                  } else{                                          return true;                                 }                          }                  }                  if (offset > 0){                          setValue(countArray[offset] - 1);                          return false;                  } else{                          return true;                 }          }          /**          *           * 测试程序          *           *           *           * @param startValue          *           *            测试匹配数中包含9的个数          *           * @param startTime          *           *            程序启动时间          */          private void test(int startValue, long startTime)          {                  // 设置9的个数                  offset = 0;                  setValue(startValue);                  while (true){                          if (checkPersentArray()){// 检查当前提交数据是否匹配                                  // 匹配且总数正好为SIZE的位数那么就是求解的值                                  if (countSumArray[offset] == SIZE){                                          success();                                 }                                  // 总数不为SIZE且当前值不在第10位即不等于0                                  if (offset != 9){                                          next();                                          continue;                                 }                                  // 总数不为SIZE且当前值在第10位。                                  if (back()){                                          break;                                 }                          } else{                                  if (back()){                                          break;                                 }                          }                  }                  System.out.println(Thread.currentThread() + " End,Spend time "                  + (System.currentTimeMillis() - startTime) / 1000 + "s");          }          /**          *           * 主函数          */          public static void main(String[] args){                 final long startTime = System.currentTimeMillis();                  int s = MAX.divide(p(9)).intValue();                  for (int i = 0; i <= s; i++){                          // new Main().test(i, startTime);                          // 启动十个线程同时运算                          final int startValue = i;                          new Thread(new Runnable(){                                  public void run(){                                          new Demo2().test(startValue, startTime);                                 }                          }).start();                  }          }          private static final BigInteger ZERO = new BigInteger("0");          private static final BigInteger MIN;          private static final BigInteger MAX;          /**          *           * 0-SIZE间的BigInteger          */          private static final BigInteger n(int i){                  return (BigInteger) ht.get("n_" + i);         }          /**          *           * 0-9的次方的BigInteger          */          private static final BigInteger p(int i){                  return (BigInteger) ht.get("p_" + i);         }          /**          *           * 用于缓存BigInteger数据并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger          */          private static Hashtable<String, Object> ht = new Hashtable<String, Object>();          static {                  int s = SIZE < 10 ? 10 : SIZE;                  for (int i = 0; i <= s; i++){                          ht.put("n_" + i, new BigInteger(String.valueOf(i)));                  }                  for (int i = 0; i <= 10; i++){                          ht.put("p_" + i, new BigInteger(String.valueOf(i)).pow(SIZE));                  }                  MIN = n(10).pow(SIZE - 1);                  MAX = n(10).pow(SIZE).subtract(n(1));          }  }
作者: qq415997288    时间: 2016-6-1 00:14
目前还解决不了你的问题
作者: students    时间: 2016-6-2 23:20
我也不会,有答案了吗,发出来看看
作者: 765237684    时间: 2016-6-2 23:23
看了一脸蒙.求大神吧
作者: zhangquan    时间: 2016-6-3 09:31
要考虑下N= 21时,所定义的变量类型是否超出范围,然后把每位数字的立方和加起来,判断是否与本数相等,还有就是要考虑下每位数字怎么取的。可以使用与10取商、取余,来得到每位上的数字,21位数和3位数都一样做法,不过就是麻烦了些
作者: 土菠萝    时间: 2016-6-3 13:12
zhangquan 发表于 2016-6-3 09:31
要考虑下N= 21时,所定义的变量类型是否超出范围,然后把每位数字的立方和加起来,判断是否与本数相等,还 ...

试了你就知道了
作者: 车前子008    时间: 2016-6-3 20:19
package test3;

import java.math.BigInteger;

public class Flower {
        //求一个数的x次方
        public static BigInteger p(int x){
                BigInteger base = BigInteger.ONE;
                for(int i=0;i<21;i++){
                        base = base.multiply(BigInteger.valueOf(x));
                }
                return base;
        }
        //求和
        public static void ji_suan(BigInteger[] pw,int[] nn){
               
                BigInteger sum = BigInteger.ZERO;
                for(int i = 0;i<10;i++){
                        sum = sum.add(pw[i].multiply(BigInteger.valueOf(nn[i])));
                       
                }
               
                String s = ""+sum;
                if(s.length()!=21)
                        return;
               
                //确定和中各个数字出现多少次数
                int[] nn2 = new int[10];
                for(int i=0;i<21;i++){
                        nn2[s.charAt(i)-'0']++;
                }
                //测试是否与nn[]中各个对应位置数目相同
                for(int i=0;i<10;i++){
                        if(nn[i] != nn2[i])
                                return;
                }
                System.out.println(s);
        }
       
        public static void f(BigInteger[] pw,int[] nn,int cur,int use){
                if(cur==9){
                        nn[9] =21-use;
                        ji_suan(pw,nn);
                        return;
                }
                for(int i=0;i<=21-use;i++){
                        nn[cur]=i;
                        f(pw,nn,cur,use+i);
                }
        }
        //主函数
        public static void main(String[] args){
                BigInteger[] pw = {p(0),p(1),p(2),p(3),p(4),p(5),p(6),p(7),p(8),p(9)};
                //0~9在21位数中出现的次数
                int[] nn = new int[10];
               
                f(pw,nn,0,0);
        }

}

作者: 土菠萝    时间: 2016-6-4 08:37
车前子008 发表于 2016-6-3 20:19
package test3;

import java.math.BigInteger;

Exception in thread "main" java.lang.StackOverflowError
        at util.Flower.f(Flower.java:40)
        at util.Flower.f(Flower.java:47)
        at util.Flower.f(Flower.java:47)
        at util.Flower.f(Flower.java:47)
        at util.Flower.f(Flower.java:47)
        at util.Flower.f(Flower.java:47)
        at util.Flower.f(Flower.java:47)
        at util.Flower.f(Flower.java:47)
作者: wzl100520    时间: 2016-6-5 10:59
  1. public static void main(String[] args) {
  2.                 for(int i=100;i<=999;i++)
  3.                 {
  4.                         int one = i%10;
  5.                         int two = i/10%10;
  6.                         int three = i/10/10%10;
  7.                         //拿到立方和
  8.                         int sum = one*one*one+two*two*two+three*three*three;
  9.                         //将立方和与所给数据进行比较
  10.                         if(sum==i){
  11.                                 System.out.println(i);
  12.                         }
  13.                 }
  14.         }
复制代码

n=3,,我只能做这么多来,
作者: 车前子008    时间: 2016-6-6 09:02
这个程序我之前看过  但是我的笔记本运行出现错误StackOverflowError  看来程序需要优化  你再参照一下别的代码吧  我只能帮到你这里了
作者: 土菠萝    时间: 2016-6-6 11:39
车前子008 发表于 2016-6-6 09:02
这个程序我之前看过  但是我的笔记本运行出现错误StackOverflowError  看来程序需要优化  你再参照一下别的 ...

不要呀,我很需要这个题目的思路来学习一下
作者: yanwenyong    时间: 2016-6-6 19:48
话说这个题目太恶心了  谁没事算这么自杀脑细胞的题  大体的思路已经出锅,但是至于说N=21  三思而行, 我让N=7就卡了我多少分钟的(反正现在正在运行没有停下的意思)总而言之,真爱电脑,谨慎添加N

具体实现以及逻辑思路看下方

  1. import java.util.ArrayList;


  2. public class Flower {

  3.         /**
  4.          * @param args
  5.          */
  6.         public static void main(String[] args) {
  7.                 //此处设置N建议不要太大,太大电脑会卡,如果想要为技术现身可以设置成21,就怕等半小时
  8.                 int N = 8;
  9.                 //此处设置一个集合,用于添加符合条件的数据
  10.                 //其实数组不是不可以,但是考虑到数据的长度,最好还是用集合
  11.                 ArrayList<Long> al = new ArrayList<Long>();
  12.                 //此处设置随机一个整数的位数上的数字
  13.                 long[] wei = new long[N];

  14.                 //进行循环从1开始算起 如果小于10的N次方  其实最大就是N位数
  15.                 //例如 10的4次方就是 10*10*10*10 = 10000 小于10000就是9999 四位数
  16.                 for(long i = 1; i<Math.pow(10, N);i++){
  17.                         //该处用于获取这个整数的每个位上的对应的数字
  18.                         //具体规律  
  19.                         /**
  20.                          * 假如 i = 64812;  那么久是5位数  N = 5 wei[]数组的长度就是5
  21.                          * wei[0] = i%10/1;
  22.                          * wei[1] = i%100/10;
  23.                          * wei[3] = i%1000/100;
  24.                          * wei[4] = i%10000/1000;
  25.                          * wei[5] = i%100000/10000;
  26.                          * 根据规律  
  27.                          * wei[n] = i%10^(n+1)/10^n  注 10^n 表示10的n次方
  28.                          * java中关于乘方的方法是Math.pow(n,m); 表示n的m次方
  29.                          * 最后得出结论
  30.                          * wei[5] = {2,1,8,4,6} 其实这个数据的顺序就是十位数的每个位数的倒序排列
  31.                          * */
  32.                         for(int n = 0; n<N ; n++){
  33.                                 wei[n] = (i%((long)Math.pow(10, (1+n)))/((long)Math.pow(10, n)));
  34.                         }
  35.                         //此处为算出这个数是几位数
  36.                         //不要以为N就完事,因为N是最大位数,
  37.                         //这里默认为1到N+1位数只间的所有的数
  38.                         /**
  39.                          * 根据规律
  40.                          * 1位数肯定小于10
  41.                          * 2位数肯定小于100
  42.                          * 3位数肯定小于1000
  43.                          * 以此类推
  44.                          * n位数肯定小于10^n
  45.                          * 所以说获得了该数的位数
  46.                          * */
  47.                         int k = 0;
  48.                         for(int d = 1; d <= N ; d++){
  49.                                 if(i < Math.pow(10, d)){
  50.                                         k = d;
  51.                                         break;
  52.                                 }
  53.                         }
  54.                         //最后代表每个位的数字也获取了,
  55.                         //代表这个十位数数字的位数k也有了
  56.                         //尽情相乘吧
  57.                         //记得加入一个总数值  
  58.                         //循环里循环一次表示某一位上的数字的乘方运算结束添 加到total里面
  59.                         //最后循环结束 总的数据也出来了
  60.                         long total = 0;
  61.                         for(int c = 0; c < N ; c++){
  62.                                 total = total + (long)Math.pow(wei[c], k);
  63.                         }
  64.                        
  65.                         //最终运算出的数据同给出的数据进行比较,
  66.                         //假如相等那么就把该数据添加到集合中
  67.                         if(total == i){
  68.                                 al.add(total);
  69.                         }
  70.                 }
  71.                 //所有的数据循环完毕打印出集合 这里不用遍历 集合已经重写了
  72.                 //toString方法保证可以打印出所有的数据
  73.                 //完美!!!!!
  74.                 System.out.println(al);
  75.                
  76.         }

  77. }
  78. //写在最后的话:
  79. //什么答案不对?是N位数,不是从1开始到N位数的最大?
  80. //好吧 ,这个也不怕  修改最外层循环
  81. //for(long i = 1; i<Math.pow(10, N);i++)
  82. //改成
  83. //for(long i = (long) Math.pow(10, (N-1))); i<Math.pow(10, N);i++)


  84. //最最后别怪我没提醒你  前面的N不要太大 我设置成了10 结果运行了30分钟没有结果
  85. //要不你试试21然后告诉我答案?
复制代码


作者: ancheng    时间: 2016-6-6 21:44
车前子008 发表于 2016-6-6 09:02
这个程序我之前看过  但是我的笔记本运行出现错误StackOverflowError  看来程序需要优化  你再参照一下别的 ...

http://stackoverflow.com/
作者: 黑猫的消失    时间: 2016-6-12 08:47
fanhongwei1105 发表于 2016-6-1 00:03
package dome;  import java.math.BigInteger;  import java.util.Hashtable;  public class Demo2{         /*           ...

同学。。。论坛回复里有一个代码插入的功能,你这样直接复制黏贴可读性几乎为0




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