简化多重循环
#include <stdio.h>#include <time.h>int power(int a,int b){ int t=1,i; for (i=0;i<b;i++) t*=a; return t;}int main(int argc, char *argv[]){ double t0=clock(); int a,b,c,d,e,f,g; for (a=1;a<=9;a++) for (b=0;b<=9;b++) for (c=0;c<=9;c++) for (d=0;d<=9;d++) for (e=0;e<=9;e++) for (f=0;f<=9;f++) for (g=0;g<=9;g++) { int num=1000000*a+100000*b+10000*c+1000*d+100*e+10*f+g; if (num==power(a,7)+power(b,7)+power(c,7)+power(d,7)+power(e,7)+power(f,7)+power(g,7)) printf(" %d ",num); } printf("\n耗时： %f s",(clock()-t0)/CLOCKS_PER_SEC); return 0;}#include <stdio.h>#include <time.h>int R[7];int power(int a,int b){ int t=1,i; for (i=0;i<b;i++) t*=a; return t;}void recursion(int L) { if (L>6) { int a,b,c,d,e,f,g; a=R[0]; b=R[1]; c=R[2]; d=R[3]; e=R[4]; f=R[5]; g=R[6]; int num=1000000*a+100000*b+10000*c+1000*d+100*e+10*f+g; if (num==power(a,7)+power(b,7)+power(c,7)+power(d,7)+power(e,7)+power(f,7)+power(g,7)) printf(" %d ",num); } else { for (R[L]=((L==0)?1:0);R[L]<=9;R[L]++) { recursion(L+1); } }}int main(int argc, char *argv[]){ double t0=clock(); recursion(0); printf("\n耗时： %f s",(clock()-t0)/CLOCKS_PER_SEC); return 0;}
[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出
[解决办法]
可以充分简化for循环结构，不过执行效率稍微差一些：
#include <stdio.h>#include <time.h>int power(int a, int b){ int t = 1; int i; for(i = 0; i < b; i++) t *= a; return t;}int main(int argc, char* argv[]){ double t0 = clock(); int a, b, c, d, e, f, g; unsigned int num; unsigned int n; for(num = 1000000; num <= 9999999; num++) { n = num; a = n / 1000000; n -= a * 1000000; b = n / 100000; n -= b * 100000; c = n / 10000; n -= c * 10000; d = n / 1000; n -= d * 1000; e = n / 100; n -= e * 100; f = n / 10; n -= f * 10; g = n; if(num == power(a, 7) + power(b, 7) + power(c, 7) + power(d, 7) + power(e, 7) + power(f, 7) + power(g, 7)) printf(" %d ", num); } printf("\n耗时： %f s", (clock() - t0) / CLOCKS_PER_SEC); return 0;}
[解决办法]
这是数学。
用 mathematica ， 一句命令
In[2]:= Select[Range[2^20], Total[IntegerDigits[#]^IntegerLength[#]] == # &]
Out[2]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, \
407, 1634, 8208, 9474, 54748, 92727, 93084, 548834}
------解决方案--------------------
1L，4L都挺不错的答案。
[解决办法]
{ clock_t t0=clock(); int V[7] = {1}; while( V[0] <= 9 ) { int num1=1000000*V[0]+100000*V[1]+10000*V[2]+1000*V[3]+100*V[4]+10*V[5]+V[6]; int num2=power(V[0],7)+power(V[1],7)+power(V[2],7)+power(V[3],7)+power(V[4],7)+power(V[5],7)+power(V[6],7); if ( num1 == num2 ) { printf( " %d ", num1 ); } ++V[6]; for( int i=6; i>0 && V[i]>9; --i ) { V[i] -= 10; ++V[i-1]; } } printf("\n耗时： %f s\n",double(clock()-t0)/CLOCKS_PER_SEC); }
[解决办法]
#include <stdio.h>#include <time.h>int power(int a, int n){ int t = 1; while (n != 0) { if ((n & 1) == 1) t = t * a; a = a * a; n = n >> 1; } return t;}void func(int * a, int d, int cur) //C without defaullt args{ int i; if (d == 0) { int num=0; int pow_sum=0; int t=1; for (i=0; i<cur; i++) { num+=a[cur-1-i]*t; pow_sum+=power(a[i], cur); t*=10; } if (num==pow_sum) printf("%d ", num); } else { for (i=cur==0 ? 1 : 0; i <= 9; i++) { a[cur] = i; func(a, d - 1, cur + 1); } }}int main(int argc, char *argv[]){ clock_t t0=clock(); int a[10]; int i; for(i=3; i<=8; i++) { func(a, i, 0); printf("\n"); } printf("\nElapsed： %0.2f s\n",(float)(clock()-t0)/CLOCKS_PER_SEC); return 0;}
[解决办法]
#include <stdio.h>#include <time.h> #define MAXDIG 7int main(){ double start=clock(); int dig,n,i,t,d,k,sum; for(dig=1;dig<MAXDIG+1;dig++) { for(d=1,i=1;i<dig;i++) { d*=10; } printf("(%d) digit find start!\n",dig); for(n=d; n<10*d; n++) { for(sum=0,t=n;t ;t/=10) { for(k=1,i=0;i<dig;i++) { k*=t%10; } sum+=k; } if(sum==n) printf("%d\n",n); } printf("-------------------------------------\n"); } printf("Timing : %f s \n",(clock()-start)/CLOCKS_PER_SEC); return 0;}
[解决办法]
#include <stdio.h>
#include <stdlib.h>
int split(int num,int a[])
{
int l=0;
while(num)
{
a[l++]=num%10;
num/=10;
}
return l;
}
int sumPower(int n,int a[],int p[])
{
int i;
int s=0;
for(i=0;i<n;i++)
{
s=s+p[a[i]];
}
return s;
}
int main(int argc, char *argv[])
{
int i,k;
int n;
int l,l0=2;
int pow[10]={0,1,4,9,16,25,36,49,64,81};
int digits[9];
int count=0;
for(k=100;k<1000000000;k++)
{
l=split(k,digits);
if(l>l0)
{
l0=l;
for(i=0;i<10;i++)
pow[i]*=i;
}
n=sumPower(l,digits,pow);
if(n == k)
{
printf("\n(%4d) %10d",++count,k);
}
}
printf("\nEscaped time : %10.3f\n",clock()/1000.0);
system("PAUSE");
return 0;
}
[解决办法]
上一层楼是曾经解过的
对LZ标题的回答如下：
for (a=1;a<=9;a++)
for (b=0;b<=9;b++)
for (c=0;c<=9;c++)
for (d=0;d<=9;d++)
for (e=0;e<=9;e++)
for (f=0;f<=9;f++)
for (g=0;g<=9;g++)
构成一个矩阵：
多行三列
每一行对应一个循环变量，可根据循环层数确定行数。
三列的内容是：这个循环变量的起点、终点和循环当前值----即前2个为循环变量的“界”，后一个是“值”
最内层循环先变。。。。变到界外，上一层再变。。。。
视矩阵为一个栈，栈顶是内层循环：先操作栈顶，出界后再移至新栈顶（上一层）。。改动循环值后再恢复原栈。。。
基于这个“数据结构”，循环、递归都可以
[解决办法]
这是前几天做的，与LZ的可变循环层数（重数）要求类似，只不过循环控制如下
for(a=1; a=N; a++)
for(b=a+1;b=N+1;b++)
for(c=b+1;b=N+2;c++)
.................
LZ的问题是每个循环变量为常数界的
我的问题是每个循环变量为变数界的----但变的规律是简单可循的
供参考
/**********************************************
古尺长M个单位，上面只有N个标记，但能测量出1----M间的任一长度
关系：
M=3,6,9,13,17,23,29,36,43
N=1,2,3, 4, 5, 6, 7, 8, 9
求解给出(M,N)时N个标记的位置
注：是M-1个对象中选N个的组合问题！
************************************************/
#include <stdio.h>
#include <stdlib.h>
/*求下一个组合码（n个数）*/
void NextComb(int loop[][2], int n)
{
int i,j,upFlag=0;
for(i=n-1; i>=0; i--)
{
loop[i][0]++; /*最内重循环变量自增*/
if(loop[i][0]<loop[i][1] && upFlag==0)
return ;
upFlag = 1;
if(loop[i][0]<loop[i][1] && upFlag==1)
{
for(j=i+1; j<n; j++)
{
loop[j][0]=loop[j-1][0]+1;
}
break;
}
}
}
void ClearRuler(int ruler[], int m)
{
int i;
for(i=1; i<=m; i++)
ruler[i]=0;
}
int TestRuler(int ruler[],int m)
{
int i;
for(i=1; i<=m; i++)
if(ruler[i]==0)
return 0;
return 1;
}
#define N 7
#define M 29
int main(int argc, char *argv[])
{
int loop[N][2]; /*第零列是循环变量的值，第一列是循环变量的右界*/
int i;
long long int count=0;
long long int total=1;
int stars[N+2]={0}; /*N个标记加左右端点，左端点恒为0*/
int ruler[M+1]={0}; /*尺长M，则标记范围为1至M-1*/
int l,r; /*任两个左右标记的位置*/
int min=M-1-N > N ? N : M-1-N;
stars[N+1]=M; /*右端点等于尺长M*/
/*N重循环的控制矩阵*/
for(i=0; i<N; i++)
{
loop[i][0]=i;
loop[i][1]=M-N+i;
printf("(%5d)",loop[i][1]);
}
/*求组合数total=C(M-1,N)作为循环次数控制*/
for(i=1; i<=min; i++)
total = total * (M-i) / i;
printf("total=%lld\n",total);
/*一重循环代替N重循环*/
for(count=0; count<total; count++)
{
/*由当前组合码生成标记位置*/
for(i=0; i<N; i++)
{
stars[i+1] = loop[i][0] + 1;
}
/*求任两个标记（含端点）间的距离*/
for(l=0; l<N+1; l++)
for(r=l+1; r<=N+1; r++)
ruler[stars[r]-stars[l]] = 1;
/*输出符合题意的解*/
if(TestRuler(ruler,M))
{
for(i=1; i<=N; i++)
printf("%8d",stars[i]);
printf("\n");
}
/*求下一个组合*/
ClearRuler(ruler,M);
NextComb(loop, N);
}
system("PAUSE");
return 0;
}
[解决办法]
改写已经没什么意思了,优化一下性能吧
下面的代码基本上已经让编译器没什么发挥空间了,release和debug版本性能相差不大.
int V[7] = {1};
int power_diff_map[11];
int power_diff_map2[11];
power_diff_map[10] = 0;
power_diff_map2[10] = -power(9,7);
for( int i=1; i <=9; ++i ) {
power_diff_map[i] = power(i,7)-power(i-1,7);
power_diff_map2[i] = power_diff_map[i] + power_diff_map2[10];
}
int num1=1000000;
int num2=1;
for( int i=6; i>0; ) {
if ( V[i]>9 ) {
V[i] = 0;
++V[i-1];
num2 += power_diff_map2[V[i-1]];
if ( V[i-1] > 9 ) {
--i;
continue;
} else {
i = 6;
}
}
if ( num2 == num1 ) {
printf( " %d ", num1 );
}
++V[6];
num2 += power_diff_map[V[6]];
++num1;
}