- 浏览: 287426 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
zh1159007904:
大侠,你这个程序的递归部分看不懂,能不能麻烦解释一下递归的思路 ...
求21位水仙花数(C语言实现) -
shenma_IT:
我是一楼的神马_CS哦 再次表示感谢!!
求21位水仙花数(C语言实现) -
shenma_IT:
好 万分感谢 !!
求21位水仙花数(C语言实现) -
Touch_2011:
shenma_CS 写道你好! 我看了你的代码 有好多让我佩服 ...
求21位水仙花数(C语言实现) -
Touch_2011:
乘法是模拟数学上两个数相乘,但在处理进位方面可能有点不同。比如 ...
求21位水仙花数(C语言实现)
/* * 21位水仙花数 */ #include<stdio.h> #include<string.h> #include<time.h> #define DIGIT 21 char pow[DIGIT][50]={0};//存储0到9的DIGIT次方 int countNumber[10];//0-9的个数 char powDigit[10][DIGIT+1][DIGIT*3];//存储(0-9的21次方)*(0-9的个数) char countDigit[][3]={"0","1","2","3","4","5","6","7","8","9","10","11","12", "13","14","15","16","17","18","19","20","21"}; //大整数加法 void add(char* result,char* a,char* b) { int temp[50]={0}; int k=0,j,i; i=strlen(a)-1,j=strlen(b)-1; //相加 while(i>=0 && j>=0){ temp[k++]=(a[i--]-'0')+(b[j--]-'0'); } while(i>=0) temp[k++]=a[i--]-'0'; while(j>=0) temp[k++]=b[j--]-'0'; //处理进位,使temp中各个元素的值在0--9之间 for(i=0;i<k;i++){ temp[i+1]+=temp[i]/10; temp[i]%=10; } while(temp[i]>9){ temp[i+1]+=temp[i]/10; temp[i]%=10; i++; } //把结果存入result字符串中 k=i; j=0; for(i=k;i>=0;i--){ if(j==0 && temp[i]==0) continue; result[j++]=temp[i]+'0'; } if(j==0) result[j++]='0'; result[j]=0; } //大整数减法(a>b) void sub(char* result,char* a,char* b) { int temp[50]={0}; int k=0,j,i; i=strlen(a)-1,j=strlen(b)-1; //相减 while(i>=0 && j>=0){ temp[k++]=(a[i--]-'0')-(b[j--]-'0'); } while(i>=0) temp[k++]=a[i--]-'0'; //使temp中各个元素的值在0--9之间 for(i=0;i<k-1;i++){ if(temp[i]<0){ temp[i]+=10; temp[i+1]-=1; } } //把结果存入result字符串中 k=i; j=0; for(i=k;i>=0;i--){ if(j==0 && temp[i]==0) continue; result[j++]=temp[i]+'0'; } if(j==0) result[j++]='0'; result[j]=0; } //大整数乘法 void multiply(char* result,char* a,char* b) { int temp[50]={0}; int k=0,j,i; int len1=strlen(a),len2=strlen(b); //相乘 for(i=len1-1;i>=0;i--){ k=len1-1-i; for(j=len2-1;j>=0;j--){ temp[k++]+=(a[i]-'0')*(b[j]-'0'); } } //处理进位,使temp中各个元素的值在0--9之间 for(i=0;i<k;i++){ temp[i+1]+=temp[i]/10; temp[i]%=10; } while(temp[i]>9){ temp[i+1]+=temp[i]/10; temp[i]%=10; i++; } //把结果存入result字符串中 k=i; j=0; for(i=k;i>=0;i--){ if(j==0 && temp[i]==0) continue; result[j++]=temp[i]+'0'; } if(j==0) result[j++]='0'; result[j]=0; } //给pow数组赋值,计算出0到9的DIGIT次方 void init() { int i,j; strcpy(pow[0],"0"); strcpy(pow[1],"1"); for(i=2;i<=9;i++){ pow[i][0]='1'; for(j=1;j<=DIGIT;j++) multiply(pow[i],pow[i],countDigit[i]); } for(i=0;i<10;i++) for(j=0;j<=DIGIT;j++) multiply(powDigit[i][j],pow[i],countDigit[j]); } //判断是否是水仙花数 int judge() { int i,temp; static char sum[50]={'0',0};//保存上一次的结果 int tempCountNum[10]={0}; static int laseNum[10]={0};//保存上一次的各个数字的个数 for(i=1;i<10;i++){ if((temp=countNumber[i]-laseNum[i])<0){ sub(sum,sum,powDigit[i][-temp]); laseNum[i]+=temp; } else if(temp>0){ add(sum,sum,powDigit[i][temp]); laseNum[i]+=temp; } } for(i=0;i<DIGIT;i++) switch(sum[i]){ case '0':tempCountNum[0]+=1;break; case '1':tempCountNum[1]+=1;break; case '2':tempCountNum[2]+=1;break; case '3':tempCountNum[3]+=1;break; case '4':tempCountNum[4]+=1;break; case '5':tempCountNum[5]+=1;break; case '6':tempCountNum[6]+=1;break; case '7':tempCountNum[7]+=1;break; case '8':tempCountNum[8]+=1;break; case '9':tempCountNum[9]+=1;break; } for(i=0;i<10;i++) if(countNumber[i]!=tempCountNum[i]) return 0; puts(sum); return 1; } //寻找DIGIT位水仙花数 void findNumber(int n,int count) { int i,max=DIGIT; int start=0; if(n==0){ countNumber[0]=DIGIT-count; judge(); return; } switch(n){ case 9:max=9;break; case 8:max=21;break; default:max=20;break; } for(i=max;i>=start;i--){ countNumber[n]=i; if(count+i>DIGIT) continue; if(countNumber[9]==0 && countNumber[8]<10) return; findNumber(n-1,count+i); } } void main() { int start=clock(); init(); printf("21位水仙花数有:\n"); findNumber(9,0); printf("用时:%d ms\n",clock()-start); }
- 21位水仙花数.zip (1.7 KB)
- 下载次数: 23
评论
6 楼
zh1159007904
2012-03-05
大侠,你这个程序的递归部分看不懂,能不能麻烦解释一下递归的思路,谢谢!!
5 楼
shenma_IT
2011-12-31
我是一楼的神马_CS哦 再次表示感谢!!
4 楼
shenma_IT
2011-12-31
好 万分感谢 !!
3 楼
Touch_2011
2011-12-28
shenma_CS 写道
你好! 我看了你的代码 有好多让我佩服的地方,真的,我是群上看到这连接,点击看到的 嗨!废话不多说,我想问下大侠你那大整数乘法那我看不懂 能不能说详细一点啊!
乘法是模拟数学上两个数相乘,但在处理进位方面可能有点不同。比如数a乘以数b,把a的个位数依次乘以b的每一位,a的个位乘完b的一位时并不急于进位,而是把每次相乘的结果保存加起来作为一个数组元素保存在数组中....最后再处理进位问题。
其他:这个程序主要在于代码优化,主要是要减少调用大整数加减乘函数的次数。第一次写出这个程序,运行时间是90秒左右、后来采用先存储(0-9的21次方)以空间换时间、优化到30秒左右,最后再judge函数中采用保存上一次结果的方法(有点动态规划的味道),时间优化到10秒左右。这些优化不是一次就想到的,是我跟另外一个同学一起想到的。所以其实我并不是什么大侠
还有就是:在java提供的大整数类中是采用int数组来处理大整数的,感觉效率会高一些。我还有个同学他是我们几个人中最早写出这个程序的,时间只有7秒,但是我们都看不懂他的代码。
如果你有更优化的算法,记得给我留言啊
2 楼
Touch_2011
2011-12-28
乘法是模拟数学上两个数相乘,但在处理进位方面可能有点不同。比如数a乘以数b,把a的个位数依次乘以b的每一位,a的个位乘完b的一位时并不急于进位,而是把每次相乘的结果保存加起来作为一个数组元素保存在数组中....最后再处理进位问题。
1 楼
shenma_CS
2011-12-26
你好! 我看了你的代码 有好多让我佩服的地方,真的,我是群上看到这连接,点击看到的 嗨!废话不多说,我想问下大侠你那大整数乘法那我看不懂 能不能说详细一点啊!
发表评论
-
二叉查找树(二叉排序树)的详细实现
2011-10-22 13:18 1318博客地址: http://blog.csdn.net/tou ... -
确定参赛者名单(C语言实现)
2011-07-10 10:39 1587/* 2011第二届国信蓝点 ... -
整数划分(C语言实现)
2011-07-10 10:35 4988/* 整数的划分问题。 如,对于正整数n=6,可以分划为 ... -
几种全排列的算法(C语言实现)
2011-07-07 00:14 6331/* * 几种排列组合的算法 */ #incl ... -
Playfire加密算法(C语言实现)
2011-07-06 10:13 3001这是C语言选拔赛最后一题,题目如下: /* ... -
浅析贪心算法
2011-07-05 17:46 13851.基本思路: a.顾名思义,贪心算法总是作出在当前看来最好 ... -
浅析动态规划算法
2011-07-05 15:30 17931、 ... -
浅析递归
2011-07-02 20:40 20651.递归的思想: 设计一个递归函数,明确这个递归函数的定义, ... -
浅析分治法
2011-07-02 13:54 22771、分治法思想: 将一个难以直接解决的大问题,分割成一些规模 ... -
浅析回溯算法
2011-06-29 22:48 29141、回溯法的基本思想 (1)在确定解空间的组织结构 ... -
高精度计算
2011-06-27 14:06 10401.大整数加法 2.大整数减法 3.大整数乘法 4.大整 ... -
浅析模拟算法
2011-06-27 07:58 18761.描述 有些问题难以找到公式或规律来解决,可以按 ... -
农夫过河的四种解法
2011-06-25 14:21 6935/* * 题目描述:有一个农夫,带着一只狼、一只羊、一颗白 ... -
各种排序算法的实现(C语言实现)
2011-06-17 22:31 1722/* * 各种基本排序算法实现(以由小到大为例) */ ... -
二叉查找树(C语言实现)
2011-06-15 23:47 2578/* * 构造一颗二叉查找树,实现树的插入、删除等基本操作 ... -
哈希表查找(C语言实现)
2011-06-15 13:38 11434/* * 题目:给定一个全部由字符串组成的字典,字符串全部 ... -
索引查找之英语词典(C语言实现)
2011-06-14 22:48 5526/* * 题目:英语词典。所有的单词存放在dictionary ... -
求最短路径的两种算法(C语言实现)
2011-06-11 11:23 28400求这个有向网中任意两点的最短路径 /* ... -
拓扑排序(C语言实现)
2011-06-10 23:09 3159对这个有向图进行拓扑排序 /* * 拓扑排序(采用邻 ... -
最小生成树(C语言实现)
2011-06-10 21:30 8847求这个网的最小生成树 /* * 普里姆算法和克鲁斯卡 ...
相关推荐
水仙花数c语言程序 C语言中的水仙花数,是指一个 n 位数,它的每个位上的数字的n次方之和等于它本身。比如,153就是一个水仙花数,因为 1^3 + 5^3 + 3^3 = 153,这样的数字在数学上称为“自幂数”。 水仙花数是一类...
“水仙花说”是一个三位说,其各位数字立方和等于改数本身,本程序用c实现求水仙花数
程序中的数字范围可以自己改,很简单. 利用for()循环很简单就找到水仙花数。
一个21位的整数,它的各个位数的21次方的和加起来等于它本身. 要求:程序在三分钟内完成,C语言实现. (有注释)
水仙花数是指一个 3 位数,它的每个位上的数字的 3次幂之和等于它本身(例如:1^3 + 5^3+ 3^3 = 153)。 输入代码: #include #include<math.h> main() { int a,b,c,n; n = 100; while(n) { a = (n % 10)...
C语言编程实现输出100—999之间的水仙花数
多方法实现的水仙花数c语言.zip
C语言程序设计-调用函数fun判断一个三位数是否水仙花数;在main函数中从键盘输入一个三位数,并输出判断结果;请编写fun函数;说明:所谓水仙花数是指一3位数,其各位数字立方和等于该数本身;例如:153是一个水仙花数,...
水仙花数c语言程序 水仙花数(Narcissistic Number)是指一个n位数,它的每个位上的数字的n次幂之和等于它本身。例如,153就是一个三位的水仙花数,因为13+53+33=15313+53+33=153。 用两种方式 C语言实现水仙花数的...
利用多重循环实现求水仙花数.所谓“水仙花数”是指一个三位数,其各位数字立方和等于该数 本身。例如:153是一个“水仙花数”,因为153=1的三次方+5的三次方+3的三次方
水仙花数 水仙花数(Narcissistic number)也被称为超完全数字不变数(pluperfect digital invariant, PPDI)、自恋数、自幂数、阿姆斯壮数或阿姆斯特朗数(Armstrong number),水仙花数是指一个 3 位数,它的每个...
c语言水仙花数 一、水仙花数的定义 所谓"水仙花数"是指一个三位数,其各位数字立方和等于该数 本身。例如:153是一个"水仙花数",因为153=1的三次方+5的三次方+3的三次方。 二、解题思路 程序分析:利用for循环...
C#求水仙花数的算法实例
水仙花数c语言程序
水仙花数的实现是一个比较经典的算法题,今天我们首先在vfp中来实现它。 首先我们了解一下什么是“水仙花数”。所谓水仙花数是指一个n位数,其各位数字立方和等于该数本身的值,例如:153=13+53+33 ,所以153是一个...
题目:打印出所有的 “水仙花数 “,所谓 “水仙花数 “是指一个三位数,其各位数字立方和等于该数本身。 例如:153是一个 “水仙花数 “,因为153=1的三次方+5的三次方+3的三次方。 实现代码如下 #include #...
基于c语言代码实现的计算水仙花数
基于linux系统用C语言编写的菜单,能密码登录,密码最多输入3次,菜单功能包含:水仙花数,判断闰年和判断素数, 其中三个菜单必须采用子函数完成。