8.1 在缺少函数原型的函数调用中,编译器是如何处理的?
答,编译器先假定调用是正确的，同时还假定被调用函数将返回一个整型值，如果调用事实上是错误的，编译器不能捕获这个错误，要运行这个程序才知道错了；如果被调用函数返回的不是整数，也将导致错误。
8.2 一个定义返回值类型为T1的函数，但该函数体内的return语句却返回一个类型为T2的表达式，调用会发生什么情况？
答：如果编译器通过算术转换能够把表达式为T2的类型转换为T1的类型时，程序能正常运行；否则，编译器将捕获到这个错误。
8.3 一个定义返回值类型为void的函数，但该函数返回一个值，这将导致什么错误？
答：这是一个语法错误。
8.4 一个定义返回值类型为非void的函数，但该函数没有返回一个值。这将导致什么后果？
答：ANSI C认为这种行为是未定义的。未定义的行为其后果是无法预料的。
8.5 如果函数的返回值类型不是int类型，并且函数定义出现在函数调用之后，当缺少函数原型声明会发生什么情况？
答：有些编译器认为这是一个语法错误。这当然是幸运的。但ANSI C并不检测这个错误，因此，如果编译器认定函数返回一个整型值，它将产生整数指令处理这个值，如果这个值实际上不是整型值，其结果通常是错误的。
8.6 传递给函数的参数个数、类型和顺序应该与函数定义匹配，编译器能够用函数原型校验函数调用是否正确。但对于那些没有原型的函数，如果传递的实参与形参不匹配，会出现什么情况？
答：如果定义在前，调用在后，参数个数不匹配这个错误将被捕获；类型不匹配将实参自动进行类型提升，例如，char和short类型的实参被转换为int型，float类型将向double类型转换。如果调用在前，定义在后，其结果不可预料。
8.7 为什么说在一个表达式内部调用没有返回值的函数将是一个严重的错误？
答：因为该表达式的值将是不可预测的。
8.8 对于如下定义语句：
int x = 10；
其定义点出现在函数外部和函数内部时，它们在行为上有什么不同？
答：出现在函数外部时，它是外部变量，仅被初始化一次；出现在函数内部时，它是自动变量，每次进入该代码块时都被初始化一次。
8.9 如果在某代码块内有如下定义语句：
extern int a；
其中a是自动变量。试问：它在语法上是否有错？为什么？
答：它在语法上没有错误。因为关键字extern对自动变量不起作用，也就不能改变自动变量的链接属性，extern在这个定义语句中是多余的。但是，如果定义者的本意是想在此处引用其它函数定义的自动变量a，那他在概念上犯了一个大错误。
8.10 下面的程序存在什么错误？为什么？
#include <stdio.h>
float f(float,int);
int main()
{
float x = 3.14;
static int y = f(x,3);
printf("%f",y);
}
float f(float x,int y)
{
return x+y;
}
答：存在编译错。因为只能用常量表达式初始化一个静态变量，而函数调用不是一个常量表达式。
8.11 编写一个函数，对给定的整数value，函数返回该值中值为1的位的个数。
算法分析：根据整数在机内的表示形式，可以采用逐位右移的方法来统计它含“1”的个数。下面是它的一种比较简洁的实现方案：
int count_bits(unsigned value)
{
int ones;
for(ones = 0; value != 0; value >>= 1)
if((value &1) != 0)
ones += 1; /* 如果最低位为1，计数器的值加1 */
return ones;
}
8.12 写一个函数，对有n个元素的float型指针数组，要求函数返回一个指针，指向那n个float型数中最大数。它的函数原型为：
float *NumMax(float *p[],int n)；
算法分析：设置一个指针pMax和一个指针数组p[]，pMax用于指向那个最大的数。算法思想是：pMax初始化为指向p[0]所指向的对象，而p[0]指向第一个float数，通过for循环，使p[i]所指对象与pMax所指对象相比较，并将pMax更新为指向其中的较大者。这样当循环终止时，pMax必指向那个最大的数。下面是它的一种实现方案：
float* max(float* p[],int n)
{
float* pMax = p[0];
int i;
for(i = 1; i < n; i++)
if(*p[i] > *pMax) pMax = p[i];
return pMax;
}
8.13仿照例8.6编程：魔术师的猜牌术。魔术师手拿13张迭在一起的黑桃牌，牌面朝下。对观众说：我不看牌，只数数就可以猜到每张牌是什么。接着，魔术师将最上面的那张牌数为1，把它翻过来正好是黑桃A，将黑桃A放在桌子上，然后按顺序从上到下数手上的余牌，第二次数1、2，将第一张牌放在这迭牌的下面，将第二张牌翻过来，正好是黑桃2，也将它放在桌子上，第三次数1、2、3，将前面两张依次放在这迭牌的下面，再翻第三张牌正好是黑桃3。这样依次进行将13张牌全翻出来，准确无误。问魔术师手中的牌原始顺序是怎样安排的？
算法分析：本题与例8.6的求解思路类似，请参考教材，这里不再赘述。所不同的是，这里的空盒数每次要递增1。下面所给程序完全仿照例8.6。
#include <stdio.h>
#include<stdlib.h>
#define N 13
void print(void);
int pick(int,int);
int a[N] = {0};
int main(void)
{
int i,pos,index = 0; /* index 为数组下标 */
a[0] = 1;
for(i = 2; i <= N; ++i)
{
pos = pick(i,index);
a[pos] = i;
index = pos;
}
print();
return EXIT_SUCCESS;
}
int pick(int i,int index) /* 从当前位置index开始，找一个合适的空盒 */
{
int count = 1; /* 对空盒计数 */
do{
if(index>N-1) index = 0; /* 到达数组尾端，下标从头开始 */
if(a[index]) index++; /* 跳过非空的盒子 */
else{ if(count==i) return index; /* 找到合适的空盒位置 */
index++;count++; /* 对空盒计数，数组下标指向下一个盒子 */
}
}while(count<=i); /* 控制空盒计数为I */
}
void print(void) /* 输出 */
{
int i;
printf("The original order of %d cards is:\n",N);
for(i = 0; i < N; i++)
printf("%d,",a[i]);
printf("\b%c\n",' ');
}
8.14 任取一个十进制整数，将其倒过来后与原数相加，得到一个新的整数后重复以上步聚，则最终可得到一个回文数。回文数的这一形成规则目前还属于一个猜想，尚未得到数学上的证明。有些回文数要经历上百个步骤才能获得。请编程验证。
算法分析：题目中给出的处理过程很清楚。显然，这里的主要问题是如何将原数倒过来，其方法在教材中已经解决。整个程序在结构上可以考虑用三个函数实现，即main函数、求一个数的反序数和判断是否是回文数函数。程序如下：
#include<stdio.h>
#define MAX 4294967295 /* 32位unsigned long类型的最大值 */
unsigned long reverse( unsigned long);
int isPalindrome(unsigned long);
int main(void)
{
unsigned long Num,Sum;
int count = 0;
printf("Please enter a number optionaly:");
scanf("%ld",&Num);
printf("The generation process of palindrome:\n");
while(!isPalindrome((Sum=reverse(Num))+Num))?
{ /* 判整数与其反序之和是否回文数 */
if(Sum + Num >= MAX)
{
printf("input error,break.\n");break;
}
else
{
printf("[%d]:%ld + %ld = %ld\n",++count,Num,Sum,Sum+Num);
Num += Sum;
}
}
printf("[%d]:%ld + %ld = %ld\n",++count,Num,Sum,Sum+Num);?
}
unsigned long reverse(unsigned long Num)/* 求输入整数的反序数 */
{
unsigned long reNum;
for(reNUM = 0;Num > 0;Num /= 10)
reNum = reNum * 10 + Num % 10;
return reNum;
}
int isPalindrome(unsigned long iNum)? /* 断给定的整数是否是回文数 */
{
if(reverse(iNum) == iNum) return 1; /* 若是回文数则返回１*/
else return 0; /* 否则返回０ */
}
8.15 写一函数，用二分法在多个字符串中查找给定的串。其函数原型为：
char *binary(char *sp[],char *s,int n)；
其中的三个参数含义是：
（1）sp：指针，它指向备查的多个串的指针数组
（2）s,指针，它指向要查找的串
（3）n,备查串的个数算法分析：二分法查找又称为折半查找，它的基本思想是：反复的将数组分为两部分，然后在可能包含目标值的那部分中进行查找。由于二分法查找的前提是要求被查找对象是已经排好序的，因此，如果这个前提已经成立，算法就很简单。已知备查的n个字符串存储于一个指针数组中，下面是它的一个实现方案。
char *binary(char *sp[],char *s,int n)
{
int low = 0,high,mid;
high = n-1;
while(low <= higt)
{
mid = (low + high) / 2;
if( strcmp(s,sp[mid]) < 0 ) /* 如果s<sp[mid]，strcmp返回负数 */
high = mid-1;
else
if(strcmp(s,sp[mid]) > 0) /* 如果s>sp[mid]，strcmp返回正数 */
low=mid+1;
else return sp[mid]; /* 目标已经找到 */
}
return 0;
}
8.16 用递归法求解,
0 m=0,n>=0
g(m,n)=
g(m-1,2n)+n m>0,n>=0
算法分析：由于递归式已经显式给出，递归结束的条件为m = 0，于是可以直接写出它的递归函数。下面用一个完整的程序验证该函数的正确性。
#include<stdio.h>
int g(int m,int n)
{
if(m == 0) return 0;
else return g(m-1,2*n)+n;
}
int main()
{
int m,n,val;
printf( "Input m and n," );
scanf("%d%d",&m,&n);
val = g(m,n);
printf( "g(%d,%d)+%d = %d",m-1,2*n,n,val );
return 0;
}
8.17 编写一函数digit(n,k),它把数n从右边起的第k位数字的值给出来,其中n为正整数，若n的位数不足k，则返回值0。
算法分析：这是数字分离技术的简单应用，连续使用k次“%”“/”运算就可以把数n的第k位数字提取出来。下面是同一种方法的两种写法：
方法一：
#include<stdio.h>
int digit(int n,int k)
{
int val;
do{
val = n % 10;
n = n / 10;
k--;
}while( k > 0 );
return val;
}
方法二：
int digit(int n,int k)
{
int i = 0,val;
do{
val = n % 10;
n /= 10;
i++;
if(i == k)
return val;
}while(n != 0);
return 0;
}
8.18 编写一递归函数，函数返回值为a[i]～a[n]间的最大数的下标（0≤i≤n）。
算法分析：对任意给定的i，从第i个位置开始，逐个与后面的比较，每次比较总是保留当前那个最大数的下标。显然，除了i不断增加外，每一步的操作都是一样的。据此，我们可以考虑用递归实现。下面是它的一个实现方案。
#include<stdio.h>
#define N 9
int a[N]={3,4,66,4,955,5,8,12,881}; /* 一个示意性的例子 */
int main()
{
int maxloca(int); /* 函数声明 */
printf("\nIndex = %d\n",maxloca(0) ); /* 为简便起见，假设i = 0 */
}
int maxloca(int i )
{
int index;
if(i == N-1) index = i;
else
{
index = maxloca(i+1);
index = a[i] > a[index]? i,index;
}
return index;
}
8.19 用递归法求解级数：
y=1+1/x+1/x2+1/x3+…直到某一项1/xn ≤10-6时为止。
算法分析：显然，递归项是1/xn，n == 0，1，2，…，用库函数y = pow(1.0/x,n++)可以很方便地实现；y <= pow(0.1,6)是递归结束的条件。一个完整的程序如下：
#include<stdio.h>
#include<math.h>
int n = 0;
float progression(int x) /* 递归求级数 */
{
float item;
item = pow(1.0/x,n++);
if(item <= pow(0.1,6)) return 0.0;
else return（progression(x)+item）;
}
int main()
{
float x;
printf("Input x = ");
scanf("%f",&x);
printf("y = %f",progression(x));
return 0;
}
8.20 设计一递归函数，计算一个自然数有多少种“加”表示法。如：5有七种：
5，4+1，3+2，3+1+1，2+2+1,
2+1+1+1，1+1+1+1+1。
算法分析：这是一个数字分解问题，每一次的有效分解都是问题的一个解。
#include <stdio.h>
int main()
{
int n,m,p = 0,pks(int,int);
printf("Input an integer n (n>0)：");
scanf("%d",&n);
for(m = n; m >= 1; m--)
p += pks(n,m);
printf("%d has %ld kinds \n",n,p);
}
int pks(int ttl,int max)
{
int p = 0;
int m = t = ttl - max;
if(max == ttl)
return 1;
if(t <= max)
{
while(m >= 1)
p += pks(t,m--);
return p;
}
while(max >= 1)
p += pks(t,max--);
return p;
}
8.21 设m，n均为自然数，m可表示为一些不超过n的自然数之和，函数fun(m,n)的值为这种表示方式的数目。例fun(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。用递归函数实现其功能。
算法分析：本题与8.20题的区别就是被分解的数字不能大于n。
#include <stdio.h>
int fun(int,int);
int main()
{
int a;
a = fun(6,4);
printf("a = %d\n",a);
}
int fun(int m,int n)
{
if(m == 1) return 1;
if(n == 1) return 1;
if(m < n) return fun(m,m);
if(m == n) return(1 + fun(m,n-1));
return(fun(m,n-1) + fun(m-n,n));
}
8.22 设有n个正整数元素的集合存放于数组a中，每个数组元素中存放一个集合元素。对给定的整数k(a[i]<k，i=1,2,…,n)，求满足所给条件的子集：子集中各元素之和等于k。
算法分析：此问题称为“子集和问题”。求解时利用数组S作为栈，栈中最终存放所求子集各元素在a中的序号（下标）。
#include <stdio.h>
#define N 6
#define K 30
int total;
void printsubset(int a[],int s[],int sp)
{
int i;
printf("%d = %2d",K,a[s[1]]);
for(i = 2;i <= sp;i++) printf("+%2d",a[s[i]]);
printf("\n");
total++;
}
int main()
{
int a[N+1],s[N+1],i,j,sp,t,finish,m=0;
printf("\n\ninput %d data<%d:",N,K);
for(i = 1;i <= N;i++) scanf("%d",&a[i]);
total=0;
for(j = 1;j <= N;j++)
{
sp = 0; t = K; i = j; finish = 0;
do{
if(t>=a[i])
{
sp++;
s[sp] = i;
t = t-a[i];
if(t==0) i = N;
}
i++;
while(i > N)
if(sp > 1)
{
if(t == 0) printsubset(a,s,sp);
t = t+a[s[sp]];
i = s[sp]+1; sp--;
}
else{
finish = 1;
i = 1;
}
}while(finish = =0);
}
printf("total= %d\n",total);
}
8.23 找出1～n的自然数中任意m个自然数的所有组合，每种组合中，自然数按递增序输如；如：设n=6，则有序列：1，2，3，4，5，6；当m=3时，有组合：
1 2 3
1 2 4
1 2 5
1 2 6
1 3 4
1 3 5
┆
5 6
方法一：算法的基本思路是:
①设置一个数组a[1..m]用于存放某种组合各位上的数字，第一种组合为123…m.
②把最末位（第m位）逐次加1，如果达到n，退至第m-1位，如果第m-1位上的数已达到其最大值n-1,再退到第m-2位，如此继续。
③一般地，将当前处理的第t位（t<m）数字a[t]在原值基础上加1，然后第t+1位至第m位上的数字变成：
a[t]+1,a[t]+2,…,a[t]+m-1
④返回②，直到每位均以达到各自的最大值为止。
#include <stdio.h>
#define N 10
#define M 6
int out(int a[])
{
int i,t;
for(i = 1;i <= M,i++) printf("%3d",a[i]);
printf("\n");
t = M;
return t;
}
int main()
{
int a[M+1],k,t;
for(k = 1;k <= M;k++) a[k] = k;
Out;
do{
if(a[t] == N-M+t) –-t;
else{
a[t]++;
if(t < M)
for(k = t+1;k <= M;k++) a[k] = a[k-1]+1;
out;
}
}while(t!=0);
}
方法二：
#include <stdio.h>
#define M 500
int num[M],m,n;
void change(int a){
if(num[a]!=n-m+a)
num[a]++;
else {
change(a-1);
num[a]=num[a-1]+1;
}
} /* change */
main(){
int k;
printf("Input n\n"); scanf("%d",&n);
printf("Input m\n"); scanf("%d",&m);
for(k=1;k<=m;k++)
num[k]=k;
do{
for(k=1;k<=m;k++)
printf("%d",num[k]);
putchar('\n');
if(num[1]==n-m+1)
break;
change(m);
}while(1);
return 0;
}
方法三：
# include<stdio.h>
# define max 100
main(){
int i,j,k,s,m,a[max];
printf("输入最大的自然数:\n"); scanf("%d",&s);
a[0]=1;
for(i=1;i<=s-1;i++)
a[i]=a[i-1]+1;
printf("每个组合的数的个数:\n"); scanf("%d",&m);
for(i=0;i<=s-m;i++)
for(j=i+1;j<=s-m+1;j++)
for(k=j+1;k<=s-m+2;k++)
printf("%d\t%d\t%d\n",a[i],a[j],a[k]);
return 0;
}
方法四：
#include<stdio.h>
#define N 15
main(){
int i,a[15],j,k,m,n;
printf("input two integer\n"); scanf("%d%d",&n,&m);
if(n<m||n>15) printf("input is wrong\n");
else{
for(j=0;j<=m-1;j++) a[j]=j+1;
do{
for(i=0;i<=m-1;i++) printf("%4d",a[i]);
printf("\n");
if(a[0]==n-m+1) break;
ghh,;
for(i=0;i<=m-1;i++)
if(a[i]==n) {
a[i-1]++; for(k=i;k<=m-1;k++)
{a[k]=a[k-1]+1;a[m-1]--; }
goto ghh;
}
a[m-1]++;
} while(a[0]<n-m+2); //do
}
return 0;
}
答,编译器先假定调用是正确的，同时还假定被调用函数将返回一个整型值，如果调用事实上是错误的，编译器不能捕获这个错误，要运行这个程序才知道错了；如果被调用函数返回的不是整数，也将导致错误。
8.2 一个定义返回值类型为T1的函数，但该函数体内的return语句却返回一个类型为T2的表达式，调用会发生什么情况？
答：如果编译器通过算术转换能够把表达式为T2的类型转换为T1的类型时，程序能正常运行；否则，编译器将捕获到这个错误。
8.3 一个定义返回值类型为void的函数，但该函数返回一个值，这将导致什么错误？
答：这是一个语法错误。
8.4 一个定义返回值类型为非void的函数，但该函数没有返回一个值。这将导致什么后果？
答：ANSI C认为这种行为是未定义的。未定义的行为其后果是无法预料的。
8.5 如果函数的返回值类型不是int类型，并且函数定义出现在函数调用之后，当缺少函数原型声明会发生什么情况？
答：有些编译器认为这是一个语法错误。这当然是幸运的。但ANSI C并不检测这个错误，因此，如果编译器认定函数返回一个整型值，它将产生整数指令处理这个值，如果这个值实际上不是整型值，其结果通常是错误的。
8.6 传递给函数的参数个数、类型和顺序应该与函数定义匹配，编译器能够用函数原型校验函数调用是否正确。但对于那些没有原型的函数，如果传递的实参与形参不匹配，会出现什么情况？
答：如果定义在前，调用在后，参数个数不匹配这个错误将被捕获；类型不匹配将实参自动进行类型提升，例如，char和short类型的实参被转换为int型，float类型将向double类型转换。如果调用在前，定义在后，其结果不可预料。
8.7 为什么说在一个表达式内部调用没有返回值的函数将是一个严重的错误？
答：因为该表达式的值将是不可预测的。
8.8 对于如下定义语句：
int x = 10；
其定义点出现在函数外部和函数内部时，它们在行为上有什么不同？
答：出现在函数外部时，它是外部变量，仅被初始化一次；出现在函数内部时，它是自动变量，每次进入该代码块时都被初始化一次。
8.9 如果在某代码块内有如下定义语句：
extern int a；
其中a是自动变量。试问：它在语法上是否有错？为什么？
答：它在语法上没有错误。因为关键字extern对自动变量不起作用，也就不能改变自动变量的链接属性，extern在这个定义语句中是多余的。但是，如果定义者的本意是想在此处引用其它函数定义的自动变量a，那他在概念上犯了一个大错误。
8.10 下面的程序存在什么错误？为什么？
#include <stdio.h>
float f(float,int);
int main()
{
float x = 3.14;
static int y = f(x,3);
printf("%f",y);
}
float f(float x,int y)
{
return x+y;
}
答：存在编译错。因为只能用常量表达式初始化一个静态变量，而函数调用不是一个常量表达式。
8.11 编写一个函数，对给定的整数value，函数返回该值中值为1的位的个数。
算法分析：根据整数在机内的表示形式，可以采用逐位右移的方法来统计它含“1”的个数。下面是它的一种比较简洁的实现方案：
int count_bits(unsigned value)
{
int ones;
for(ones = 0; value != 0; value >>= 1)
if((value &1) != 0)
ones += 1; /* 如果最低位为1，计数器的值加1 */
return ones;
}
8.12 写一个函数，对有n个元素的float型指针数组，要求函数返回一个指针，指向那n个float型数中最大数。它的函数原型为：
float *NumMax(float *p[],int n)；
算法分析：设置一个指针pMax和一个指针数组p[]，pMax用于指向那个最大的数。算法思想是：pMax初始化为指向p[0]所指向的对象，而p[0]指向第一个float数，通过for循环，使p[i]所指对象与pMax所指对象相比较，并将pMax更新为指向其中的较大者。这样当循环终止时，pMax必指向那个最大的数。下面是它的一种实现方案：
float* max(float* p[],int n)
{
float* pMax = p[0];
int i;
for(i = 1; i < n; i++)
if(*p[i] > *pMax) pMax = p[i];
return pMax;
}
8.13仿照例8.6编程：魔术师的猜牌术。魔术师手拿13张迭在一起的黑桃牌，牌面朝下。对观众说：我不看牌，只数数就可以猜到每张牌是什么。接着，魔术师将最上面的那张牌数为1，把它翻过来正好是黑桃A，将黑桃A放在桌子上，然后按顺序从上到下数手上的余牌，第二次数1、2，将第一张牌放在这迭牌的下面，将第二张牌翻过来，正好是黑桃2，也将它放在桌子上，第三次数1、2、3，将前面两张依次放在这迭牌的下面，再翻第三张牌正好是黑桃3。这样依次进行将13张牌全翻出来，准确无误。问魔术师手中的牌原始顺序是怎样安排的？
算法分析：本题与例8.6的求解思路类似，请参考教材，这里不再赘述。所不同的是，这里的空盒数每次要递增1。下面所给程序完全仿照例8.6。
#include <stdio.h>
#include<stdlib.h>
#define N 13
void print(void);
int pick(int,int);
int a[N] = {0};
int main(void)
{
int i,pos,index = 0; /* index 为数组下标 */
a[0] = 1;
for(i = 2; i <= N; ++i)
{
pos = pick(i,index);
a[pos] = i;
index = pos;
}
print();
return EXIT_SUCCESS;
}
int pick(int i,int index) /* 从当前位置index开始，找一个合适的空盒 */
{
int count = 1; /* 对空盒计数 */
do{
if(index>N-1) index = 0; /* 到达数组尾端，下标从头开始 */
if(a[index]) index++; /* 跳过非空的盒子 */
else{ if(count==i) return index; /* 找到合适的空盒位置 */
index++;count++; /* 对空盒计数，数组下标指向下一个盒子 */
}
}while(count<=i); /* 控制空盒计数为I */
}
void print(void) /* 输出 */
{
int i;
printf("The original order of %d cards is:\n",N);
for(i = 0; i < N; i++)
printf("%d,",a[i]);
printf("\b%c\n",' ');
}
8.14 任取一个十进制整数，将其倒过来后与原数相加，得到一个新的整数后重复以上步聚，则最终可得到一个回文数。回文数的这一形成规则目前还属于一个猜想，尚未得到数学上的证明。有些回文数要经历上百个步骤才能获得。请编程验证。
算法分析：题目中给出的处理过程很清楚。显然，这里的主要问题是如何将原数倒过来，其方法在教材中已经解决。整个程序在结构上可以考虑用三个函数实现，即main函数、求一个数的反序数和判断是否是回文数函数。程序如下：
#include<stdio.h>
#define MAX 4294967295 /* 32位unsigned long类型的最大值 */
unsigned long reverse( unsigned long);
int isPalindrome(unsigned long);
int main(void)
{
unsigned long Num,Sum;
int count = 0;
printf("Please enter a number optionaly:");
scanf("%ld",&Num);
printf("The generation process of palindrome:\n");
while(!isPalindrome((Sum=reverse(Num))+Num))?
{ /* 判整数与其反序之和是否回文数 */
if(Sum + Num >= MAX)
{
printf("input error,break.\n");break;
}
else
{
printf("[%d]:%ld + %ld = %ld\n",++count,Num,Sum,Sum+Num);
Num += Sum;
}
}
printf("[%d]:%ld + %ld = %ld\n",++count,Num,Sum,Sum+Num);?
}
unsigned long reverse(unsigned long Num)/* 求输入整数的反序数 */
{
unsigned long reNum;
for(reNUM = 0;Num > 0;Num /= 10)
reNum = reNum * 10 + Num % 10;
return reNum;
}
int isPalindrome(unsigned long iNum)? /* 断给定的整数是否是回文数 */
{
if(reverse(iNum) == iNum) return 1; /* 若是回文数则返回１*/
else return 0; /* 否则返回０ */
}
8.15 写一函数，用二分法在多个字符串中查找给定的串。其函数原型为：
char *binary(char *sp[],char *s,int n)；
其中的三个参数含义是：
（1）sp：指针，它指向备查的多个串的指针数组
（2）s,指针，它指向要查找的串
（3）n,备查串的个数算法分析：二分法查找又称为折半查找，它的基本思想是：反复的将数组分为两部分，然后在可能包含目标值的那部分中进行查找。由于二分法查找的前提是要求被查找对象是已经排好序的，因此，如果这个前提已经成立，算法就很简单。已知备查的n个字符串存储于一个指针数组中，下面是它的一个实现方案。
char *binary(char *sp[],char *s,int n)
{
int low = 0,high,mid;
high = n-1;
while(low <= higt)
{
mid = (low + high) / 2;
if( strcmp(s,sp[mid]) < 0 ) /* 如果s<sp[mid]，strcmp返回负数 */
high = mid-1;
else
if(strcmp(s,sp[mid]) > 0) /* 如果s>sp[mid]，strcmp返回正数 */
low=mid+1;
else return sp[mid]; /* 目标已经找到 */
}
return 0;
}
8.16 用递归法求解,
0 m=0,n>=0
g(m,n)=
g(m-1,2n)+n m>0,n>=0
算法分析：由于递归式已经显式给出，递归结束的条件为m = 0，于是可以直接写出它的递归函数。下面用一个完整的程序验证该函数的正确性。
#include<stdio.h>
int g(int m,int n)
{
if(m == 0) return 0;
else return g(m-1,2*n)+n;
}
int main()
{
int m,n,val;
printf( "Input m and n," );
scanf("%d%d",&m,&n);
val = g(m,n);
printf( "g(%d,%d)+%d = %d",m-1,2*n,n,val );
return 0;
}
8.17 编写一函数digit(n,k),它把数n从右边起的第k位数字的值给出来,其中n为正整数，若n的位数不足k，则返回值0。
算法分析：这是数字分离技术的简单应用，连续使用k次“%”“/”运算就可以把数n的第k位数字提取出来。下面是同一种方法的两种写法：
方法一：
#include<stdio.h>
int digit(int n,int k)
{
int val;
do{
val = n % 10;
n = n / 10;
k--;
}while( k > 0 );
return val;
}
方法二：
int digit(int n,int k)
{
int i = 0,val;
do{
val = n % 10;
n /= 10;
i++;
if(i == k)
return val;
}while(n != 0);
return 0;
}
8.18 编写一递归函数，函数返回值为a[i]～a[n]间的最大数的下标（0≤i≤n）。
算法分析：对任意给定的i，从第i个位置开始，逐个与后面的比较，每次比较总是保留当前那个最大数的下标。显然，除了i不断增加外，每一步的操作都是一样的。据此，我们可以考虑用递归实现。下面是它的一个实现方案。
#include<stdio.h>
#define N 9
int a[N]={3,4,66,4,955,5,8,12,881}; /* 一个示意性的例子 */
int main()
{
int maxloca(int); /* 函数声明 */
printf("\nIndex = %d\n",maxloca(0) ); /* 为简便起见，假设i = 0 */
}
int maxloca(int i )
{
int index;
if(i == N-1) index = i;
else
{
index = maxloca(i+1);
index = a[i] > a[index]? i,index;
}
return index;
}
8.19 用递归法求解级数：
y=1+1/x+1/x2+1/x3+…直到某一项1/xn ≤10-6时为止。
算法分析：显然，递归项是1/xn，n == 0，1，2，…，用库函数y = pow(1.0/x,n++)可以很方便地实现；y <= pow(0.1,6)是递归结束的条件。一个完整的程序如下：
#include<stdio.h>
#include<math.h>
int n = 0;
float progression(int x) /* 递归求级数 */
{
float item;
item = pow(1.0/x,n++);
if(item <= pow(0.1,6)) return 0.0;
else return（progression(x)+item）;
}
int main()
{
float x;
printf("Input x = ");
scanf("%f",&x);
printf("y = %f",progression(x));
return 0;
}
8.20 设计一递归函数，计算一个自然数有多少种“加”表示法。如：5有七种：
5，4+1，3+2，3+1+1，2+2+1,
2+1+1+1，1+1+1+1+1。
算法分析：这是一个数字分解问题，每一次的有效分解都是问题的一个解。
#include <stdio.h>
int main()
{
int n,m,p = 0,pks(int,int);
printf("Input an integer n (n>0)：");
scanf("%d",&n);
for(m = n; m >= 1; m--)
p += pks(n,m);
printf("%d has %ld kinds \n",n,p);
}
int pks(int ttl,int max)
{
int p = 0;
int m = t = ttl - max;
if(max == ttl)
return 1;
if(t <= max)
{
while(m >= 1)
p += pks(t,m--);
return p;
}
while(max >= 1)
p += pks(t,max--);
return p;
}
8.21 设m，n均为自然数，m可表示为一些不超过n的自然数之和，函数fun(m,n)的值为这种表示方式的数目。例fun(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。用递归函数实现其功能。
算法分析：本题与8.20题的区别就是被分解的数字不能大于n。
#include <stdio.h>
int fun(int,int);
int main()
{
int a;
a = fun(6,4);
printf("a = %d\n",a);
}
int fun(int m,int n)
{
if(m == 1) return 1;
if(n == 1) return 1;
if(m < n) return fun(m,m);
if(m == n) return(1 + fun(m,n-1));
return(fun(m,n-1) + fun(m-n,n));
}
8.22 设有n个正整数元素的集合存放于数组a中，每个数组元素中存放一个集合元素。对给定的整数k(a[i]<k，i=1,2,…,n)，求满足所给条件的子集：子集中各元素之和等于k。
算法分析：此问题称为“子集和问题”。求解时利用数组S作为栈，栈中最终存放所求子集各元素在a中的序号（下标）。
#include <stdio.h>
#define N 6
#define K 30
int total;
void printsubset(int a[],int s[],int sp)
{
int i;
printf("%d = %2d",K,a[s[1]]);
for(i = 2;i <= sp;i++) printf("+%2d",a[s[i]]);
printf("\n");
total++;
}
int main()
{
int a[N+1],s[N+1],i,j,sp,t,finish,m=0;
printf("\n\ninput %d data<%d:",N,K);
for(i = 1;i <= N;i++) scanf("%d",&a[i]);
total=0;
for(j = 1;j <= N;j++)
{
sp = 0; t = K; i = j; finish = 0;
do{
if(t>=a[i])
{
sp++;
s[sp] = i;
t = t-a[i];
if(t==0) i = N;
}
i++;
while(i > N)
if(sp > 1)
{
if(t == 0) printsubset(a,s,sp);
t = t+a[s[sp]];
i = s[sp]+1; sp--;
}
else{
finish = 1;
i = 1;
}
}while(finish = =0);
}
printf("total= %d\n",total);
}
8.23 找出1～n的自然数中任意m个自然数的所有组合，每种组合中，自然数按递增序输如；如：设n=6，则有序列：1，2，3，4，5，6；当m=3时，有组合：
1 2 3
1 2 4
1 2 5
1 2 6
1 3 4
1 3 5
┆
5 6
方法一：算法的基本思路是:
①设置一个数组a[1..m]用于存放某种组合各位上的数字，第一种组合为123…m.
②把最末位（第m位）逐次加1，如果达到n，退至第m-1位，如果第m-1位上的数已达到其最大值n-1,再退到第m-2位，如此继续。
③一般地，将当前处理的第t位（t<m）数字a[t]在原值基础上加1，然后第t+1位至第m位上的数字变成：
a[t]+1,a[t]+2,…,a[t]+m-1
④返回②，直到每位均以达到各自的最大值为止。
#include <stdio.h>
#define N 10
#define M 6
int out(int a[])
{
int i,t;
for(i = 1;i <= M,i++) printf("%3d",a[i]);
printf("\n");
t = M;
return t;
}
int main()
{
int a[M+1],k,t;
for(k = 1;k <= M;k++) a[k] = k;
Out;
do{
if(a[t] == N-M+t) –-t;
else{
a[t]++;
if(t < M)
for(k = t+1;k <= M;k++) a[k] = a[k-1]+1;
out;
}
}while(t!=0);
}
方法二：
#include <stdio.h>
#define M 500
int num[M],m,n;
void change(int a){
if(num[a]!=n-m+a)
num[a]++;
else {
change(a-1);
num[a]=num[a-1]+1;
}
} /* change */
main(){
int k;
printf("Input n\n"); scanf("%d",&n);
printf("Input m\n"); scanf("%d",&m);
for(k=1;k<=m;k++)
num[k]=k;
do{
for(k=1;k<=m;k++)
printf("%d",num[k]);
putchar('\n');
if(num[1]==n-m+1)
break;
change(m);
}while(1);
return 0;
}
方法三：
# include<stdio.h>
# define max 100
main(){
int i,j,k,s,m,a[max];
printf("输入最大的自然数:\n"); scanf("%d",&s);
a[0]=1;
for(i=1;i<=s-1;i++)
a[i]=a[i-1]+1;
printf("每个组合的数的个数:\n"); scanf("%d",&m);
for(i=0;i<=s-m;i++)
for(j=i+1;j<=s-m+1;j++)
for(k=j+1;k<=s-m+2;k++)
printf("%d\t%d\t%d\n",a[i],a[j],a[k]);
return 0;
}
方法四：
#include<stdio.h>
#define N 15
main(){
int i,a[15],j,k,m,n;
printf("input two integer\n"); scanf("%d%d",&n,&m);
if(n<m||n>15) printf("input is wrong\n");
else{
for(j=0;j<=m-1;j++) a[j]=j+1;
do{
for(i=0;i<=m-1;i++) printf("%4d",a[i]);
printf("\n");
if(a[0]==n-m+1) break;
ghh,;
for(i=0;i<=m-1;i++)
if(a[i]==n) {
a[i-1]++; for(k=i;k<=m-1;k++)
{a[k]=a[k-1]+1;a[m-1]--; }
goto ghh;
}
a[m-1]++;
} while(a[0]<n-m+2); //do
}
return 0;
}
