C语言经典题目及解题思路，持续更新中。。。

吴秦

原帖由 aobai 于 2009-7-31 13:37 发表
非常好

第二题：
　caution：其实要判断这三个数是否由1~9组成且各个数组不相同，即这三个数的各位数是否覆盖了1~9，只要判断各位数字的积是否等于9！且各位数字的和是否等于45。

  能否解释下？
第七 ...

如果这三个数的各位数是否覆盖了1~9，则各位数字的积必定=1*2*3*4*5*6*7*8*9=9！，各位数字的和必定=1+2+3+4+5+6+7+8+9=45，反之如果没有覆盖1~9就不会有这结果。

顺便跟大家解释下，公司这段时间要做项目时间很紧所以就没有更新，以后一定会继续更新的不会太监的，望大家谅解！

kai0200

mark

猫博士

谢谢楼主, 收益匪浅.

吴秦

9、
【问题描述】用递归函数求解两个正整数的最大公约数的过程。
【思路】此题不需太多的思考就是运用欧几里得算法（Euclid’s algorithm）。
  摘自《The Art  of Computer Programming》volume 1：
  (Eu ...

As a careful reader,you can find that if m<n originally,the quotient in step1 will always be zero and the algorithm will always proceed to interchange m and n in this rather cumbersome fashion.
So we can add a new step :
Step0:[Ensure m>=n.]If m<n, exchange m and n.

Did you think why this algorithm is right when you read it ?(If you want to grasp computer programming or to be a mater you should always think this problem whenever or wherever you read a algorithm!)

Proof:
After step1,we have m=qn+r,for some integer q.
If r=0,then m is a multiple of n,and clearly in such a case n is the greatest common divisor of m and n.
If r!=0,note that any number that divides both m and n must divide m-qn=r,and any number that divides both n and r must divide qn+r=m;
So the set of common divisors of {m,n} is the same as the set of common divisors of {n,r}.
In particular ,the greatest common divisor of {m,n} is the same as the greatest common divisor of {n,r}.
Therefore  step3 does not change the answer to the original problem .

guojianlee

mark

icegona

第一题中如果输入的是0会是怎样一种情况?

mengxingtaxiang

好的东东值得珍藏和力挺！！！

清凉散人

加油啊，拭目以待。

第七题递归
int max(int a[],int n)
{
    if(0==n)
        return a[n];
    else   
        return (a[n]>max(a,n-1)?a[n]:max(a,n-1));   
}

改成这样才搞懂，外加还调试了几个小时。初学勿笑。

int solve(int a[],int n)
{
        if(0 == n)
                return a[n];
        else if((solve(a,n - 1) < a[n]))
                return a[n];
                else
                return solve(a, n-1);
}

[ 本帖最后由 清凉散人 于 2009-10-26 20:57 编辑 ]

清凉散人

1. 
   
2. 
   
3. #include<stdio.h>
   
4. #include<stdlib.h>
   
5. void backtrack(int n);
   
6. 
   
7. int x[8],sum=0;/*sum用于统计共有多少种方案*/
   
8. /*函数功能：回朔求解第n天至第7天的解（即第n～7天分别安排和尚几）*/
   
9. struct st
   
10. {
    
11.         int spare[8];
    
12. /*存储和尚的空闲时间，spare=0表示星期i没有空闲，spare=1表示星期i空闲,其中spare[0]不用*/
    
13. 
    
14.         int flag;
    
15. /*用于标记和尚周内是否已经工作过，flag＝0表示没挑过水，flag＝1表示已经挑过水*/
    
16. 
    
17. }monk[8]={
    
18.                 {0, 1, 0, 1, 0, 0 ,0 },
    
19.                 {1 ,0 ,0 ,0 ,0 ,1 ,0 },
    
20.                 {0, 0 ,1 ,0 ,0 ,0 ,1 },
    
21.                 {0, 0 ,0 ,0 ,1, 0, 0 },
    
22.                 {1 ,0 ,0, 1 ,0 ,1 ,0 },
    
23.                 {0 ,1 ,0 ,0 ,1 ,0 ,0 },
    
24.                 {0 ,0, 1 ,0 ,0 ,1, 1 }
    
25.                 };
    
26. 
    
27. int main (int argc, char **argv)
    
28. {
    
29.         backtrack(0);
    
30.         printf("共有%d种方案\n",sum);
    
31. }
    
32. 
    
33. void backtrack(int n)
    
34. {/*函数功能：回朔求解第n天至第7天的解（即第n～7天分别安排和尚几）*/
    
35.         int j;
    
36.         if(n>6)
    
37.         {
    
38.                 sum++;
    
39.                 printf("方案%d:\n",sum);
    
40.                 for(j=0;j<=6;j++)
    
41.                 {                        
    
42.                         printf("星期%d和尚%d挑水\n",j+1,x[j]+1);
    
43.                 }               
    
44.                 printf("\n");
    
45.         }
    
46.         else
    
47.         {
    
48.                 for(j=0;j<=6;j++)
    
49.                 {
    
50.                         x[n]=j;
    
51.                         if(monk[j].flag==0&&monk[j].spare[n]==1)
    
52.                         {//判断和尚j是否已经挑过水及和尚星期n是否有空
    
53.                                 monk[j].flag=1;        
    
54.                                 backtrack(n+1);        
    
55.                                 monk[j].flag=0;                                                
    
56.                         }                                       
    
57.                 }        
    
58.                                        
    
59.         }
    
60. }
    
61. 
    

复制代码

和尚这样挑水,这样方便调试。。

[ 本帖最后由 清凉散人 于 2009-10-25 08:34 编辑 ]

matthew_ye

2、
【问题描述】Armstrong数具有如下特征：一个n位数等于其个位数的n次方之和。如：
153＝13＋53＋33
1634＝14＋64+34+44
找出2、3、4、5位的所有Armstrong数。

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. void find_armstrong_number()
   
6. {
   
7.         char number_str[16]={0};
   
8.         int len;
   
9.         int i,j,k,total,tmp;
   
10.         for (i = 10; i < 100000; i++)
    
11.         {
    
12.                 sprintf (number_str,  "%d", i);
    
13.                 len = strlen(number_str);
    
14.                 total = 0;
    
15.                 for (j=0;j<len;j++)
    
16.                 {
    
17.                         tmp = 1;
    
18.                         for(k=0;k<len;k++) tmp *= (number_str[j]-'0');
    
19.                         total += tmp;
    
20.                 }
    
21.                 if (total == i)
    
22.                         printf("%d\n",i);
    
23.         }
    
24. }
    
25. 
    
26. int main(int argc, char *argv[])
    
27. {
    
28.         printf("output:\n");
    
29.         find_armstrong_number();
    
30.         return 0;
    
31. }
    
32. 
    

复制代码

打印结果如下：
output:
153
370
371
407
1634
8208
9474
54748
92727
93084
分别在vc和gcc上验证通过～

[ 本帖最后由 matthew_ye 于 2009-11-11 11:12 编辑 ]