• N阶楼梯问题的始基是N==1、N==2两种情况；
• 上楼可以一步上一阶，也可以一步上二阶，当上一阶时问题规模变为N-1，当上二阶时问题规模变为N-2，所以总的情况为count(n-1)+count(n-2)。

}【程序输入输出】for example

【问题描述】Armstrong数具有如下特征：一个n位数等于其个位数的n次方之和。如：

找出2、3、4、5位的所有Armstrong数。
【思路】看到此题我第一反应是用枚举法，给定m(10<=m<=99999)，首先判断m的位数n，然后判断它是否等于各位数的n次方之和。

• 定义函数int judgeDigit(int m)，用于判断给定参数m的位数；
• 定义函数int judgeEqual(int m,int n)，其中m为给定的数，n为m的位数，用于判断m是否等于各位数的n次方之和。

【程序输入输出】

注：用gcc调试就得不到153这个结果，但windows下用vc6.0就可以得到。不解中，这是编译器问题还是程序问题？
3、
【问题描述】将1,2,3,4,5,6,7,8,9共9个数分成三组,组成3个三位数,且使这3个三位数构成1:2:3的比例,例如:3个三位数192,384,576满足以上条件.192:384:576=1:2:3。试求出所有满足条件的3个三位数。

【思路】1～9组成的最小三位数是123，最大的是987，由于要满足1：2：3的关系，最小的那个数应该不到于987/3＝329。这样的话第一个数的变化范围是123～329，将这里面的数分别乘2、乘3，然后判断这三个数是���符合要求，即这三个数是否由1～9组成，而且各个数字不能相同。
即对每个数n(123<=n<=329)用枚举法。

• 定义函数int judge(int n)，用于判断整数n的各位数字是否相同，如果有想同的就返回0；否则返回1；
• 对每个数n(123<=n<=329)，2*n，3*n调用judge()函数用于判断这三个数是否由1~9组成且各个数字不相同；
• 判断n，2*n，3*n这三个数中的各位数是否相同，所以对数n*1000*1000+2*n*1000+3*n调用judge()判断。

cCODE：来自一位网友 youshuang，即用 判断各位数字的积是否等于9！且各位数字的和是否等于45。)

}【程序输入输出】

【问题描述】和尚挑水
某寺庙里7个和尚:轮流挑水，为了和其他任务不能冲突，各人将有空天数列出如下表：
和尚1: 星期二,四;
和尚2: 星期一,六;
和尚3: 星期三,日;
和尚4: 星期五;
和尚5: 星期一,四,六;
和尚6: 星期二,五;
和尚7: 星期三,六,日;
请将所有合理的挑水时间安排表
【思路】用回朔法求解（递归方式实现，当然也可以用迭代方式）。用结构体存储和尚的信息（空闲时间、是否已经挑过水标记）回朔法即每进行一步，都试图在当前部分解的基础上扩大该部分解。扩大时，首先检查扩大后是否违反了约束条件，若不违反，则扩大之，然后继续在此基础上按照类似的方法进行，直至成为完整解；若违反，则放弃该步以及它所能生成的部分解，然后按照类似的方法尝试其他可能的扩大方式，直到尝试了所有的扩大方式。  
【代码】

}【程序输入输出】

请输入和尚1的空闲时间：0 1 0 1 0 0 0
请输入和尚2的空闲时间：1 0 0 0 0 1 0
请输入和尚3的空闲时间：0 0 1 0 0 0 1
请输入和尚4的空闲时间：0 0 0 0 1 0 0
请输入和尚5的空闲时间：1 0 0 1 0 1 0
请输入和尚6的空闲时间：0 1 0 0 1 0 0
请输入和尚7的空闲时间：0 0 1 0 0 1 1

方案1:
星期1和尚2挑水
星期2和尚6挑水
星期3和尚3挑水
星期4和尚1挑水
星期5和尚4挑水
星期6和尚5挑水
星期7和尚7挑水

方案2:
星期1和尚2挑水
星期2和尚6挑水
星期3和尚7挑水
星期4和尚1挑水
星期5和尚4挑水
星期6和尚5挑水
星期7和尚3挑水

方案3:
星期1和尚5挑水
星期2和尚6挑水
星期3和尚3挑水
星期4和尚1挑水
星期5和尚4挑水
星期6和尚2挑水
星期7和尚7挑水

方案4:
星期1和尚5挑水
星期2和尚6挑水
星期3和尚7挑水
星期4和尚1挑水
星期5和尚4挑水
星期6和尚2挑水
星期7和尚3挑水

共有4种方案

5、
【问题描述】编写一个c 程序，利用如下的格里高利公式求п 的值，直到最后一项的值小于10-6 为止。

【思路】由公式可以看出，每次n 的值都会改变，这实际上就是迭代。
在程序设计中，迭代是经常使用的一种算法。使用迭代算法时要注意三个问题：

• 迭代的初始值，如本题中sum的初始值为1，n的初始值为1

• 迭代公式，这是迭代的关键，如果有几个迭代公式，要特别注意这些迭代的顺序。如i+=1和sum+=n的次序不能交换。

• 迭代终止条件。一般用一个表达式或者计数器来判断迭代式是否应该终止。

本题中迭代式中i+=1 ，i 的初始值为1 ；sum+=n or sum-=n 这通过一个标志变量flag 来控制，flag==1 时sum+=n ，flag==0 时sum-=n ，sum 的初始值为1 。终止条件为。

【代码】
cCODE:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main (int argc, char **argv)
{
int flag=0,i=1;
double n=1,sum=1;
while(n>=pow(10,-6))
{
n=(double)1/(2*i+1);
i+=1;
if(1==flag)
{
sum+=n;
flag=0;
}
else
{
sum-=n;
flag=1;
}
}
sum*=4;
printf("%lf",sum);
system("PAUSE");
return 0;
}

【程序输入输出】
No input ；
Output ：
3.141595

6、
【问题描述】编写一个c 程序，把下列数组延长到第50 项：
1 ，2 ，5 ，10 ，21 ，42 ，85 ，170 ，341 ，682
【思路】由给定的数组元素可以看出偶数项是前一项的2 倍，奇数项是前一项的2 倍加1 。
即，这是一中递推关系由前项推出后项，此题可以通过递推关系求解。
递推解题和迭代解题是很相似的，递推是通过其他变量来演化，而迭代则是通过自身不断演化。递推法的运用也有三个关键：

• 寻找递推关系。这是最重要的问题。递推关系有解析和非解析两种。解析递推关系是指能用一般数学公式描述的关系，也称递推公式。例如，本题的递推关系就是解析的。非解析递推关系是指不能用一般的数学公式描述的关系，这类关系的描述，也许本身就是一个过程。这类问题一般比较复杂，要结合其他的策略如分治法来解决。

• 递推关系必须有始基，即最小子解（针对初始规模的子解的值），没有始基，递推计算就不能开始。例如本题a1=1就是始基。

• 递推计算。即根据递推关系进行递推计算。递推计算可以由递归解析和非递归两种，递归计算是采用递归法，其形式是自顶向下，而非递归则是自底向上。本题是非递归的。

解此题还须注意一点：数列的项必须定义为double 型，因为延长到第50 项如果定义为int or float 型，数列的项会被截断即超过int 和float 的表示范围。
【代码】
cCODE:
#include<stdio.h>
#include<stdlib.h>

int main (int argc, char **argv)
{

double a1=1,a=0;
int i=1;
while(i<=50)
{
printf("%.0lf ",a1); //'.0’ is just for do not output the decimal place
i++;
if(i%2==1)
a=2*a1+1;
else
a=2*a1;
a1=a;
}
system("PAUSE");
return 0;
}
【程序输入输出】
No input ；
Output ：
1 2 5 10 21 42 85 .......（略）

7、
【问题描述】 用递归算法实现求一个数组中的最大元素。
【思路】解决递归问题可以分为两个部分，第一部分是一些特殊（基础）情况，用直接法解，即始基；第二部分与原问题相似，可用类似的方法解决（即递归），但比原问题的规模要小。
本题显然始基是a[0],关键是要找出递归关系，定义一个函数int max(int a[],int n)，其中整型a[]是一个数组，n是数组长度减1，即数组最大有效元素的下标，因为c语言中数组元素下标是从0开始的。

• 如果0==n，则a[0]就是最大的元素
• 如果n>0，则先求出a[0]到a[n-1]的最大元素，然后与a[n]比较，较大者即为最大元素。其中a[0]到a[n-1]又可以用这种方式求，此时需要将a[0],a[1]...a[n-1]看成一个由n-1个元素构成的一维数组。

【代码】
cCODE:
#include<stdio.h>
#include<stdlib.h>

int max(int a[],int n);

int main (int argc, char **argv)
{
int a[]={1,2,3,4,5,6,7,6};
printf("The max element is %d!\n",max(a,7));
/*caution:he length of a is 8,but the argument is 7*/
system("PAUSE");
return 0;
}

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));
}

【程序输入输出】
no input;
output:
The max element is 7!

8、
【问题描述】自然数的拆分：任何一个大于1的自然数N，总可以拆分成若干个自然数之和，并且有多种拆分方法。例如自然数5，可以有如下一些拆分方法：
5=1+1+1+1+1
5=1+1+1+2
5=1+2+2
5=1+4
5=2+3
【思路】 自然数的拆分可以用回溯法。
知识点：回溯法解题时，对任一解的生产，一般采用逐步扩大解的方式。每进行一步，都试图在当前部分解的基础上扩大该部分解。扩大时，首先检查扩大后是否违反了约束条件，若不违反，则扩大之，然后继续在此基础上按照类似的方法进行，直至为完全解；若违反，则放弃该步以及它生成的部分解，然后按照类似的方法尝试其他可能的扩大方式，直到已经尝试了所有的扩大方式。
回溯法解题通常包含以下三个步骤：

• 针对所给问题，定义问题的解空间；如本题对5的拆分来说，1<=拆分的数<=5。
• 确定易于搜索的解空间结构；如本题对5的拆分来说，用x[]数组来存储解，每个数组元素的取值范围都是1<=拆分的数<=5，从1开始搜索直到5。
• 搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。如本题对5的拆分来说，为了避免重复，x>=x[j](i>j)，如x[]={2,3}满足条件而x[]={3,2}就不满足条件不是可行解即无效。

回溯法通常有两种实现方式，一种是递归的方式，另一种是迭代的方式。在此就用递归方式，当然迭代的方式也可以。  
【代码】 cCODE:

 #include<stdio.h>
#include<stdlib.h>
void splitN(int n,int m);//n 是需要拆分的数，m 是拆分的进度。
int x[1024]={0},total=0 ;//total 用于计数拆分的方法数，x[] 用于存储解
int main()
{
      int n ;
      printf("please input the natural number n:");
      scanf("%d",&n);
      splitN(n,1);
      printf("There are %d ways to split natural number %d.\n",total,n);
      system("PAUSE");
      return 0 ;
}
void splitN(int n,int m)
{//n 是需要拆分的数，m 是拆分的进度。
      int rest,i,j;
      for(i=1;i<=n;i++)
      {// 从1 开始尝试拆分。
            if(i>=x[m-1])
            {// 拆分的数大于或等于前一个从而保证不重复
                  x[m]=i ;// 将这个数计入结果中。
                  rest=n-i ;// 剩下的数是n-i ，如果已经没有剩下的了，并且进度( 总的拆分个数) 大于1 ，说明已经得到一个结果。
                  if(rest==0&&m>1)
                  {
                        total++;
                        printf("%d\t",total);
                        for(j=1;j<m;j++)
                        {
                              printf("%d+",x[j]);
                        }
                        printf("%d\n",x[m]);
                  }
                  else
                  {
                        splitN(rest,m+1);// 否则将剩下的数进行进度为m+1 拆分。
                  }
                  x[m]=0;// 取消本次结果，进行下一次拆分。环境恢复，即回溯
            }
      }
}

【程序输入输出】

input:
please input the natural number n:5
output:
1 1+1+1+1+1
2 1+1+1+2
3 1+1+3
4 1+2+2
5 1+4
6 2+3
There are 6 ways to split natural number 5.

线形表a、b为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表h；

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <assert.h>
5. #define QUIT 999
7. typedef struct node
8. {
9.       int num;
10.       struct node* next; 
11. }NODE;
13. int create_list(NODE** head)
14. {
15.       int num;
16.       int i = 0;
17.       NODE* p = NULL;
18.       NODE* q = NULL;
19.       
20.       *head = (NODE*)malloc(sizeof(NODE));
21.       if(*head == NULL)
22.       {
23.             printf("head malloc error\n");
24.             return -1; 
25.       }
26.       (*head)->next = NULL;
27.       
28.       printf("input %d to end add list\n",QUIT);
29.       while(1)
30.       {
31.             p = *head; 
32.             q = (NODE*)malloc(sizeof(NODE));
33.             if(q == NULL)
34.             {
35.                   printf("head malloc error\n");
36.                   return -1; 
37.             }
38.             i++;
39.             printf("Now Please input num %d:\t",i);
40.             scanf("%d",&num); 
41.             if(num == QUIT)
42.             {
43.                   printf("end create list\n");
44.                   break;
45.             }
46.             q->num = num;
47.             while((p->next != NULL) && (p->next->num < num))
48.             {
49.                   p = p->next;
50.             }
51.             
52.             q->next = p->next;
53.             p->next = q;
54.             
55.       } 
56.       return 0; 
57. }
59. NODE* merge_list(NODE* head1,NODE* head2)
60. {
61.       assert(head1 != NULL);
62.       assert(head2 != NULL);
63.       
64.       
65.       NODE* head = (NODE*)malloc(sizeof(NODE));
66.       if(head == NULL)
67.       {
68.             printf("head malloc error\n");
69.             return NULL; 
70.       }
71.       
72.       NODE* head_tmp = head;
73.       NODE* p1 = head1->next;
74.       NODE* p2 = head2->next;
75.       
76.       while((p1 != NULL) && (p2 != NULL))
77.       {
78.             printf("p1 data is %d\t p2 date is %d\n",p1->num,p2->num);
79.             if(p1->num < p2->num)
80.             {
81.                   printf("copied %d\n",p1->num);
82.                   system("PAUSE");
83.                   head_tmp->next = p1;
84.                   p1 = p1->next; 
85.             } 
86.             else
87.             {
88.                   printf("copied %d\n",p2->num);
89.                   system("PAUSE");
90.                   head_tmp->next = p2;
91.                   p2 = p2->next; 
92.             } 
93.             head_tmp = head_tmp->next; 
94.       } 
95.       
96.       if(p1 == NULL)
97.       {
98.             head_tmp->next = p2;
99.             printf("asdas copied:\n");
100.             print_list(head_tmp);
101.       }
102.       else
103.       {
104.             head_tmp->next = p1;
105.             printf("asdas copied:\n");
106.             print_list(head_tmp);
107.       }
108.       return head; 
109. } 
110. int print_list(NODE* head)
111. {
112.       assert(head != NULL);
113.       NODE* p = head;
114.       while(p->next != NULL)
115.       {
116.             printf("%d\t",p->next->num);
117.             p = p->next; 
118.       }
119.       printf("\n"); 
120. } 
122. int main(int argc, char *argv[])
123. {
124.       NODE* head1 = NULL;
125.       NODE* head2 = NULL;
126.       
127.       create_list(&head1);
128.       create_list(&head2);
129.       
130.       printf("list1 is:\n");
131.       print_list(head1);
132.       printf("list2 is:\n");
133.       print_list(head2);
134.       printf("merged list is:\n");
135.       print_list(merge_list(head1,head2));
136.       
137.       system("PAUSE"); 
138.       return 0;
139. }

复制代码

2编写算法，从10亿个浮点数当中，选出其中最大的10000个。

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <time.h>
5. //#define INIT 10000
7. #define INIT 5
9. //#define TOTAL 100000000
11. #define TOTAL 10
13. static int count = 0;
15. typedef struct tree
16. {
17.       int num;
18.       struct tree* parent;
19.       struct tree* lchild;
20.       struct tree* rchild; 
21. }TREE;
23. TREE* add_tree(TREE** T, TREE* parent, int num)
24. {
25.       if(*T == NULL)
26.       {
27.             *T = (TREE*)malloc(sizeof(TREE));
28.             if(*T == NULL)
29.             {
30.                   printf("malloc error\n");
31.                   return NULL; 
32.             }
33.             printf("added %d\n",num);
34.             (*T)->num = num;
35.             (*T)->parent = parent;
36.             (*T)->lchild = NULL;
37.             (*T)->rchild = NULL; 
38.       }
39.       else if((*T)->num < num)
40.       return add_tree(&(*T)->rchild,*T,num); 
41.       else
42.       return add_tree(&(*T)->lchild,*T,num); 
43. }
45. int midwalk(TREE* T)
46. {
47.       if(T!=NULL)
48.       {
49.             midwalk(T->lchild);
50.             count++;
51.             if(count%10 == 0) 
52.             {
53.                   count = 0;
54.                   printf("%d\n",T->num);
55.             }
56.             else
57.             printf("%d\t",T->num);
58.             
59.             midwalk(T->rchild); 
60.       }
61.       return 0; 
62. }
64. int tree_out(TREE** T)
65. {
66.       int num = 0;
67.       TREE* p = NULL;
68.       TREE* q = NULL;
69.       TREE** tmp = T;
70.       TREE* tmp1 = *T;
71.       
72.       printf("tmp is %p\ntmp1 is %p\n",*tmp,tmp1);
73.       if(*tmp == NULL)
74.       {
75.             printf("sorry the tree is empty\n"); 
76.             return -1;
77.       } 
78.       if((*tmp)->lchild == NULL)
79.       {
80.             q = *tmp;
81.             num = q->num;
82.             *tmp = (*tmp)->rchild;
83.             printf("now head is %d\n",q->num); 
84.             free(q);
85.             q = NULL;
86.             return num; 
87.       }
88.       #if 1 
89.       while(tmp1->lchild != NULL)
90.       {
91.             p = tmp1; 
92.             tmp1 = tmp1->lchild; 
93.       } 
94.       p->lchild = tmp1->rchild;
95.       num = tmp1->num; 
96.       free(tmp1);
97.       #endif
98.       #if 0 
99.       while((*tmp)->lchild != NULL)
100.       {
101.             p = *tmp; 
102.             *tmp = (*tmp)->lchild; 
103.       } 
104.       p->lchild = (*tmp)->rchild;
105.       num = (*tmp)->num; 
106.       free(*tmp);
107.       #endif
108.       return num;
109. }
111. int minimum(TREE* T)
112. {
113.       while(T->lchild != NULL)
114.       {
115.             T = T->lchild; 
116.       } 
117.       return T->num;
118. }
120. int main(int argc, char *argv[])
121. {
122.       int i = 0;
123.       int num = 0;
124.       double j = INIT;
125.       int mini = 0;
126.       
127.       
128.       TREE* T = NULL;
129.       srand( (unsigned)time( NULL ) );
130.       
131.       for(i=0;i<INIT;i++)
132.       {
133.             num = rand(); 
134.             add_tree(&T, NULL, num); 
135.       }
136.       midwalk(T); 
137.       
138.       mini = minimum(T);
139.       for(j=INIT;j<TOTAL;j++)
140.       {
141.             num = rand();
142.             if(num > mini)
143.             {
144.                   tree_out(&T);
145.                   add_tree(&T, NULL, num);
146.                   mini = minimum(T);
147.             } 
148.       }
149.       
150.       midwalk(T); 
151.       system("PAUSE"); 
152.       return 0;
153. }