6.1一个数组中的元素可以有多少种不同的类型？
答：只有一种。一个数组中的所有元素都是同类型的。
6.2数组下标可以有哪些类型？
答：数组下标必须是整数类型。
6.3在定义一个数组的同时初始化它，但初始化列表中的值少于数组元素的个数。其余元素的值将是什么？
答：初始化列表中的值将赋值给数组前面的元素，其余元素的初值为0。
6.4当数组初始化列表中的值的个数多于数组元素的个数，将会发生什么现象？
答：将会出错。
6.5为什么必须知道“C的数组是按行序为主序存储”的？
答：因为当需要按某种顺序访问数组元素时，例如初始化数组，通过移动指针连续访问数组等等操作都与C的存储方式有关。
6.6多维数组的多个下标必须分别出现在各自的方括号对内。那么，在什么条件下，下列代码段可以通过编译而不会产生出错或警告信息：
int a[5][10];
……
b = a[2，4];
答:表达式
b = a[2，4];
等价于下面这个表达式:
b = a[4];
在这里，a[4]是一个类型为int型的常量指针。因此，只要b是一个类型为int*的指针，该段代码就不会存错。但如果将b = a[2，4]改为
b = a[2，5]
将出错。因为a[5]不存在。
6.7表达式a[i+j]和i+j[a]是否相等？
答：不妨设i = 2，j = 3。
如果a是二维数组，则a[i+j]就是a[5]，它代表数组a第5行首元素的地址，即a[5] == &a[5][0]。表达式i+j[a]即 2+3[a]，也就是a[3]+2，它代表数组a第三行第二列元素的地址,即a[3]+2 == &a[3][2]。显然两者不相等。
如果a是一维数组，由i == 2，j == 3代入a[i+j] 得 a[5]，它表示a的第5个元素。而表达式i+j[a]转换为指针表示是i+*(a+j)，它等价于i+a[j]，即a[3]+2，它表示将a[3]的值加上2。可见，a[i+j]不等于i+j[a]。
6.8设有定义
int array[3][4];
请给出下面每个表达式的值。假定数组起始位置为1000,sizeof(int) == 2。
(1) array
(2) array+2
(3) array[2]
(4) array[2]-1
(5) &array[1][2]
(6) &array[2][0]
答：(1) 1000
(2) 1016
(3) 1016
(4) 1014
(5) 1012
(6) 1016
6.9 编程生成如下矩阵:
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
算法分析：考虑到上三角矩阵和下三角矩阵（不含主对角线）元素的有序性，可分别形成矩阵元素。一种实现方案如下：
#define MAX 5
#include<stdio.h>
int main()
{
int i,j,k;
int a[MAX][MAX];
for (i = 0; i < MAX ; ++i) /* 形成上三角矩阵各元素 */
{
k = 1;
for (j = i; j < MAX ; ++j)
a[i][j] = k++;
}
for (i = 1; i < MAX ; ++i) /* 形成下三角矩阵各元素 */
for (j = 0; j <= i-1; ++j)
a[i][j] = a[i-j-1][MAX-1];
for (i = 0; i < MAX ;++i) /* 输出矩阵各元素 */
{
printf(" \n");
for (j = 0; j < MAX ; ++j)
printf("%3d",a[i][j]);
}
}
6.10 将自然数1～n2按自然数的顺序依次填入“蛇形”方阵中。一个4×4的蛇形方阵为：
1 3 4 10
2 5 9 11
6 8 12 15
7 13 14 16
算法分析：先打印上三角，再打印下三角，打印方向如下图箭头所示。用循环变量i控制行。
对上三角：当i=1时，打印一个元素，
当i=n时，打印n个元素。
对下三角：当i=1时，打印n-i个元素，
当i=n时，打印n-i+1个元素。
一种实现方案：
#define N 15
#include <stdio.h>
int main()
{
int a[N][N],i,j,k,n,d = 1;
printf("Input n= ");
scanf("%d",&n);
for(k = 1; k <= n; k++)
if(k % 2 == 1)
for(i = 1,j = k; i <= k && j >= 1; i++,j--)
a[i][j] = d++;
else
for(j = 1,i = k; j <= k && i >= 1; j++,i--)
a[i][j] = d++;
if(n % 2 == 1)
{
for(k = 1; k <= n-1; k++)
if(k % 2 == 1)
for( j = k+1,i = n; i >= k+1 && j <= n; j++,i--)
a[i][j] = d++;
else
for(j = n,i = k+1;j >= k+1 && i <= n; j--,i++)
a[i][j] = d++;
}
else
for(k = 1; k <= n-1; k++)
if(k % 2 == 1)
for(i = k+1,j = n; j >= k+1 && i <= n; i++,j--)
a[i][j] = d++;
else
for(j = k+1,i = n; i >= k+1 && j <= n; j++,i--)
a[i][j] = d++;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
printf("%4d",a[i][j]);
printf("\n\n");
}
return 0;
}
另一种实现方案：
#include <stdio.h>
#define N 15
int main()
{
int a[N][N],r,i,j,d = 1;
for(i = 0; i < N; ++i)
{
if(i % 2 == 0)
for(j = i; j >= 0; --j)
a[i-j][j] = d++;
else
for(j = 0; j <= i; ++j)
a[i-j][j] = d++;
}
for(i=1;i<N;++i)
{
if((i + N) % 2 == 0)
for(j = i,r = 1; j < N; ++r,++j)
a[N-r][j] = d++;
else
for(j = N; j > i; --j)
a[N-j+i][j-1] = d++;
}
printf("\n");
for(i = 0; i < N; ++i)
{
for(j = 0; j < N; ++j)
printf("%4d",a[i][j]);
printf("\n\n");
}
}
6.11 按自然数顺序生成“螺旋形”方阵。一个4×4的螺旋形方阵为：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
算法分析：本题看起来似乎很难。事实上，我们可以将这个螺旋方阵一分为四：先生成上面一行，接着生成右边一列，再生成下面一行，最后生成左边一列。要注意两点：与6.10题一样，用一个变量d控制当前应填入矩阵中的数，每填入一次d就加一，以保证填入的数不会出错。此其一；其二，注意控制每一行每一列的上、下界。下面是它的一个实现方案。
#define MAX 20
#include<stdio.h>
int main()
{
int i,j,d,m,n;
int a[MAX+1][ MAX+1] ; /* 数组0下标未用 */
printf("Input n= ");
scanf("%d",&n);
d = 0;
if(n % 2) m = n / 2+1; /* 变量m控制循环的次数 */
else m = n / 2;
for(i = 1; i <= m; ++i)
{
for(j = i; j <= n-i+1; ++j) /* 生成上面一行元素 */
a[i][j] = ++d;
for (j = i+1; j <= n-i+1; ++j) /* 生成右边一列元素 */
a[j][n-i+1] = ++d;
for (j = n-i; j >= i; --j) /* 生成下面一行元素 */
a[n-i+1][j]=++d;
for (j = n-i; j >= i+1; --j) /* 生成左边一列元素 */
a[j][i] = ++d;
} /* 至此，螺旋方阵已经生成 */
printf("\n"); /* 下面是输出螺旋方阵 */
for(i = 1; i <= N; ++i)
{
for(j = 1; j <= N; ++j)
printf("%4d",a[i][j]);
printf("\n\n");
}
}
6.12 编程，按递增序生成集合M最小的100个数。M的定义如下：
①?数1属于M；
② 如果x属于M，则y=2x+1和z=3x+1也属于M；
③ 再也没有别的数属于M。
算法分析：用数组存放Ｍ。对任一自然数Ｋ，若Ｋ能用Ｍ中已存在的数生成，则将Ｋ存人数组。如此依次考察自然数，则得到的必是最小的、互异的数。下面是一种实现方案：
#include<stdio.h>
int main()
{
int a[100],k,x2,x3;
a[1] = 1; x2 = 1; x3 = 1;
for(k = 2; k <= 100; k++)
if(2 * a[x2] == 3 * a[x3])
{
a[k] = 2 * a[x2++]+1; x3++;
}
else if(2 * a[x2] < 3 * a[x3])
a[k] = 2 * a[x2++]+1;
else a[k] = 3 * a[x3++]+1;
x2 = 0;
for(k = 1; k <= 100; k++)
{
printf("%4d",a[k]); ++x2;
if(x2 % 10==0) printf("\n");
}
}
另一种实现方案：
#include<stdio.h>
int main()
{
int j,m[100],y,z;
m[0] = j = 1;
y = z = 0;
while(j < 100)
{
if(m[z] * 3 >= m[y] * 2)
{
m[j] = m[y++] * 2+1;
if(m[z] * 3+1 == m[j]) z++;
}
else m[j] = m[z++] * 3+1;
j++;
}
for(j = 0; j < 100; j++)
{
printf("%6d",m[j]);
if((j + 1) % 10 == 0) printf("\n");
}
return 0;
}
6.13有一个已按升序排列的数组，现插入一个数number，要求插入后该数组仍为升序。
算法分析：这个问题可以分解为以下四步：
（1）生成一个有n个元素的有序数组a；
（2）定位插入点，设其为i；
（3）将a[i]，a[i+1]，…，a[n-1]顺序右移一位；
（4）插入新元素。
注意到插入点不外乎三种情况之一：首元素之前；末元素之后；任意两元素之间。下面就是按以上思路的一个实现方案。
#include<stdio.h>
#define MAX 50
int main()
{
int n,i,number,index,a[MAX];
/* 生成一个有n个元素的有序数组a */
printf("Input n(n<=%d)",MAX);
scanf("%d",&n);
printf("Input %d numbers to be sorted:\n",n);
for(i=0;i<=n-1;i++)
scanf("%d",&a[i]);
printf("Input the number," );
scanf("%d",&number); /* 输入欲插入的元素 */
/* 定位插入点 */
if(number >= a[n-1])
index = n; /* 插在最后 */
else if(number <= a[0])
index = 0; /* 插在最后 */
else{ /* 插在任意两元素之间 */
index = 1;
while(number > a[index])
index++;
}
/* 元素右移一位 */
for(i = n-1; i >= index; --i)
a[i+1] = a[i];
a[index]=number; /* 插入新元素 */
/* 输出插入后的结果 */
printf("sorted array are:\n");
for( i = 0; i <= n; i++)
printf("%4d",a[i]);
printf("\n");
return 0;
}
6.14 输入一正整数N(N不超过80位)，去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输出应包括所去掉的数字的位置和组成的新数。
例如,N=’178543’,S=4，删数过程如下：
178543 → 17543 → 1543 → 143 → 13
算法分析：因为N<=80，所以以字串形式输入N，使用尽可能逼近目标的贪心法来逐一删去其中S个数符，每一步总是选择一个使剩下的数最小的数符删去。之所以作出这样贪心的选择，是因为删S个数符的全局最优解，包含了删一个数符的子问题的最优解。
为了保证删1个数符后的数最小，我们按高位→低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首字符，这样形成一个新数串。然后回到串首，重复上述规则，剩下一数符……依此类推，直到删除S个数符为止。程序如下：
#include <stdio.h>
#include <string.h>
int main()
{
char a[81],c[81];
int b[80];
int len,len1,s,s1,t,k,i,j;
printf("Input the number N:");
scanf("%s",a);
printf("The wish deletes numbers,");
scanf("%d",&s);
len = len1 = strlen(a);
t = 0; s1 = s;
for(i = 0; i<len; i++)
c[i] = a[i];
for(i = 0; i < len-1; i++)
{
k = i;
for(j = i+1; j < len; j++)
if(c[j] > c[k]) k = j;
c[k] = 0;
b[t++] = k;
}
while(s)
{
k=0;
for(i = 0; i < len; i++)
if(a[i+1] > a[k]) k = i+1;
for(i = k; i < len; i++)
a[i] = a[i+1];
--len;
--s;
}
printf("\nThe new number is ");
for(i=0;i<len1-s1;i++)
printf("%c",a[i]);
printf("\n\n");
printf("There are position of to be deleted digital:");
for(i = 0; i < s1; i++)
printf("%d,",b[i]);
printf("\b%c\n ",' ');
return 0;
}
6.15 用选择法对数组中n个整数按由小到大排序。
算法分析：有多种选择排序法，教材P.135详细讨论了简单选择排序法。下面就是根据该方法编写的一个程序。
#include<stdio.h>
#define MAX 50
int main()
{
int size,i,j,k,temp,a[MAX];
printf("Input size(size<=%d),",MAX); scanf("%d",&size);
printf("Input %d numbers to be sorted:\n",size);
for(i = 0; i <= size-1; i++)
scanf("%d",&a[i]);
for(i = 0; i < size-1; i++)
{
k = i;
for(j = i+1; j < size; j++)
if(a[j] < a[k]) k = j;
if(k != i)
{
temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
printf("sorted array are:\n");
for(i = 0; i < size; i++)
printf("%d,",a[i]);
printf("\b%c\n",' ');
return 0;
}
另一种实现方案：
#include<stdio.h>
#define MAX 50
void selsort(int a[],int n)
{
int i,j,t;
for(j = 0; j < n/2; j++)
for(i = j+1; i < n-j; i++)
{
if(a[j] > a[n-j-1]) t = a[j],a[j] = a[n-1-j],a[n-1-j] = t;
if(a[i] < a[j]) t = a[j],a[j] = a[i],a[i] = t;
if(a[i] > a[n-1-j]) t = a[n-j-1],a[n-j-1] = a[i],a[i] = t;
}
}
int main()
{
int i,a[MAX],n,t;
printf("Input n(n<=%d),",MAX "); scanf("%d",&n);
printf("Input %d numbers to be sorted:\n",n);
for(i = 0; i < n; i++)
scanf("%d",&a[i]);
selsort(a,n);
printf("sorted array are:\n");
for(i = 0; i < n; i++)
printf("%d,",a[i]);
printf("\b%c\n",' ');
return 0;
}
6.16 改写例5-7，用数组实现。
算法分析：我国政府目前使用下面这些规则计算每个公民的个人月收入所得税：
含税级距X 税率（%） 速算扣除数
X≤500 5 0
500＜X≤2000 10 25
2000＜X≤5000 15 125
5000＜X≤20000 20 375
20000＜X≤40000 25 1375
40000＜X≤60000 30 3375
60000＜X≤80000 35 6375
80000＜X≤100000 40 10375
X＞100000 45 15375
例如，某公民月税前收入为4679.47元，用速算扣除法计算应纳税额为：
（4679.47-1600）*15%－125＝336.92元在例5-7中采用CASE语句设计计税器时，程序很复杂。在这里，我们改用数组来实现，计税器的设计变得很简单。下面是它的一个实现方案，其算法一目了然。
#include<stdio.h>
#include<float.h>
int main()
{
float income;
int i;
float income_limits[]
={0,500,2000,5000,20000,40000,60000,80000,100000,FLT_MAX};
float rate[] = {0,.05,.1,.15,.2,.25,.3,.35,.4,.45};
int deduction_amout[] = {0,0,24,125,375,1375,3375,6375,10375,15375};
printf("Input each month of income,");
scanf("%f",&income);
income = income - 1600.0;
for(i = 0; income > income_limits[i]; i++);
printf("tax = %f\n",income*rate[i]-deduction_amout[i]);
}
6.17 求车速。一辆以固定速度行驶的汽车，司机在上午10点看到里程表上的读数是一个对称数(即这个数从左向右读和从右向左读是完全一样的)，为95859。两小时后里程表上出现了一个新的对称数。问该车的速度是多少？新的对称数是多少？
算法分析：根据题意，设所求对称数为x，其初值为95589，对其依次递增取值，将x值的每一位分解后与其对称位置上的数进行比较，若每个对称位置上的数皆相等，则可判定x即为所求的对称数。
#include<stdio.h>
int main()
{
int t,a[5]; /* 数组a存放分解的数字位 */
long int k,x;
for(x = 95860;; x++)
{
for(t = 0,k = 100000;k >= 10;t++) /* 从高到低分解所取x值的每位*/
{/* 数字，依次存放于a[0]~a[5]中 */
a[t] = (x%k)/(k/10);
k /= 10;
}
if((a[0] == a[4]) && (a[1] == a[3]))
{
printf("The new symmetrical number kelometers is,");
printf("%d%d%d%d%d\n",a[0],a[1],a[2],a[3],a[4]);
printf("The velocity of the car is,%.2f\n",(x-95859)/2.0);
break;
}
}
}
6.18 找出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
┆
4 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 15
int main()
{
int i,a[15],j,k,m,n;
printf("Input n = "); scanf("%d",&n);
printf("Input m = "); scanf("%d",&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);
}
return 0;
}
第二种实现方案：
#include <stdio.h>
#define M 10
int a[M],m,n;
void change(int d)
{
if(a[d] != n-m+d)
a[d]++;
else{
change(d-1);
a[d] = a[d-1]+1;
}
} /* change */
int main()
{
int k;
printf("Input n\n"); scanf("%d",&n);
printf("Input m\n"); scanf("%d",&m);
for(k = 1;k <= m;k++)
a[k]=k;
do{
for(k = 1;k <= m;k++)
printf("%d",a[k]);
putchar('\n');
if(a[1] == n-m+1) break;
change(m);
}while(1);
return 0;
}
6.19 设有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);
}
答：只有一种。一个数组中的所有元素都是同类型的。
6.2数组下标可以有哪些类型？
答：数组下标必须是整数类型。
6.3在定义一个数组的同时初始化它，但初始化列表中的值少于数组元素的个数。其余元素的值将是什么？
答：初始化列表中的值将赋值给数组前面的元素，其余元素的初值为0。
6.4当数组初始化列表中的值的个数多于数组元素的个数，将会发生什么现象？
答：将会出错。
6.5为什么必须知道“C的数组是按行序为主序存储”的？
答：因为当需要按某种顺序访问数组元素时，例如初始化数组，通过移动指针连续访问数组等等操作都与C的存储方式有关。
6.6多维数组的多个下标必须分别出现在各自的方括号对内。那么，在什么条件下，下列代码段可以通过编译而不会产生出错或警告信息：
int a[5][10];
……
b = a[2，4];
答:表达式
b = a[2，4];
等价于下面这个表达式:
b = a[4];
在这里，a[4]是一个类型为int型的常量指针。因此，只要b是一个类型为int*的指针，该段代码就不会存错。但如果将b = a[2，4]改为
b = a[2，5]
将出错。因为a[5]不存在。
6.7表达式a[i+j]和i+j[a]是否相等？
答：不妨设i = 2，j = 3。
如果a是二维数组，则a[i+j]就是a[5]，它代表数组a第5行首元素的地址，即a[5] == &a[5][0]。表达式i+j[a]即 2+3[a]，也就是a[3]+2，它代表数组a第三行第二列元素的地址,即a[3]+2 == &a[3][2]。显然两者不相等。
如果a是一维数组，由i == 2，j == 3代入a[i+j] 得 a[5]，它表示a的第5个元素。而表达式i+j[a]转换为指针表示是i+*(a+j)，它等价于i+a[j]，即a[3]+2，它表示将a[3]的值加上2。可见，a[i+j]不等于i+j[a]。
6.8设有定义
int array[3][4];
请给出下面每个表达式的值。假定数组起始位置为1000,sizeof(int) == 2。
(1) array
(2) array+2
(3) array[2]
(4) array[2]-1
(5) &array[1][2]
(6) &array[2][0]
答：(1) 1000
(2) 1016
(3) 1016
(4) 1014
(5) 1012
(6) 1016
6.9 编程生成如下矩阵:
1 2 3 4 5
5 1 2 3 4
4 5 1 2 3
3 4 5 1 2
2 3 4 5 1
算法分析：考虑到上三角矩阵和下三角矩阵（不含主对角线）元素的有序性，可分别形成矩阵元素。一种实现方案如下：
#define MAX 5
#include<stdio.h>
int main()
{
int i,j,k;
int a[MAX][MAX];
for (i = 0; i < MAX ; ++i) /* 形成上三角矩阵各元素 */
{
k = 1;
for (j = i; j < MAX ; ++j)
a[i][j] = k++;
}
for (i = 1; i < MAX ; ++i) /* 形成下三角矩阵各元素 */
for (j = 0; j <= i-1; ++j)
a[i][j] = a[i-j-1][MAX-1];
for (i = 0; i < MAX ;++i) /* 输出矩阵各元素 */
{
printf(" \n");
for (j = 0; j < MAX ; ++j)
printf("%3d",a[i][j]);
}
}
6.10 将自然数1～n2按自然数的顺序依次填入“蛇形”方阵中。一个4×4的蛇形方阵为：
1 3 4 10
2 5 9 11
6 8 12 15
7 13 14 16
算法分析：先打印上三角，再打印下三角，打印方向如下图箭头所示。用循环变量i控制行。
对上三角：当i=1时，打印一个元素，
当i=n时，打印n个元素。
对下三角：当i=1时，打印n-i个元素，
当i=n时，打印n-i+1个元素。
一种实现方案：
#define N 15
#include <stdio.h>
int main()
{
int a[N][N],i,j,k,n,d = 1;
printf("Input n= ");
scanf("%d",&n);
for(k = 1; k <= n; k++)
if(k % 2 == 1)
for(i = 1,j = k; i <= k && j >= 1; i++,j--)
a[i][j] = d++;
else
for(j = 1,i = k; j <= k && i >= 1; j++,i--)
a[i][j] = d++;
if(n % 2 == 1)
{
for(k = 1; k <= n-1; k++)
if(k % 2 == 1)
for( j = k+1,i = n; i >= k+1 && j <= n; j++,i--)
a[i][j] = d++;
else
for(j = n,i = k+1;j >= k+1 && i <= n; j--,i++)
a[i][j] = d++;
}
else
for(k = 1; k <= n-1; k++)
if(k % 2 == 1)
for(i = k+1,j = n; j >= k+1 && i <= n; i++,j--)
a[i][j] = d++;
else
for(j = k+1,i = n; i >= k+1 && j <= n; j++,i--)
a[i][j] = d++;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
printf("%4d",a[i][j]);
printf("\n\n");
}
return 0;
}
另一种实现方案：
#include <stdio.h>
#define N 15
int main()
{
int a[N][N],r,i,j,d = 1;
for(i = 0; i < N; ++i)
{
if(i % 2 == 0)
for(j = i; j >= 0; --j)
a[i-j][j] = d++;
else
for(j = 0; j <= i; ++j)
a[i-j][j] = d++;
}
for(i=1;i<N;++i)
{
if((i + N) % 2 == 0)
for(j = i,r = 1; j < N; ++r,++j)
a[N-r][j] = d++;
else
for(j = N; j > i; --j)
a[N-j+i][j-1] = d++;
}
printf("\n");
for(i = 0; i < N; ++i)
{
for(j = 0; j < N; ++j)
printf("%4d",a[i][j]);
printf("\n\n");
}
}
6.11 按自然数顺序生成“螺旋形”方阵。一个4×4的螺旋形方阵为：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
算法分析：本题看起来似乎很难。事实上，我们可以将这个螺旋方阵一分为四：先生成上面一行，接着生成右边一列，再生成下面一行，最后生成左边一列。要注意两点：与6.10题一样，用一个变量d控制当前应填入矩阵中的数，每填入一次d就加一，以保证填入的数不会出错。此其一；其二，注意控制每一行每一列的上、下界。下面是它的一个实现方案。
#define MAX 20
#include<stdio.h>
int main()
{
int i,j,d,m,n;
int a[MAX+1][ MAX+1] ; /* 数组0下标未用 */
printf("Input n= ");
scanf("%d",&n);
d = 0;
if(n % 2) m = n / 2+1; /* 变量m控制循环的次数 */
else m = n / 2;
for(i = 1; i <= m; ++i)
{
for(j = i; j <= n-i+1; ++j) /* 生成上面一行元素 */
a[i][j] = ++d;
for (j = i+1; j <= n-i+1; ++j) /* 生成右边一列元素 */
a[j][n-i+1] = ++d;
for (j = n-i; j >= i; --j) /* 生成下面一行元素 */
a[n-i+1][j]=++d;
for (j = n-i; j >= i+1; --j) /* 生成左边一列元素 */
a[j][i] = ++d;
} /* 至此，螺旋方阵已经生成 */
printf("\n"); /* 下面是输出螺旋方阵 */
for(i = 1; i <= N; ++i)
{
for(j = 1; j <= N; ++j)
printf("%4d",a[i][j]);
printf("\n\n");
}
}
6.12 编程，按递增序生成集合M最小的100个数。M的定义如下：
①?数1属于M；
② 如果x属于M，则y=2x+1和z=3x+1也属于M；
③ 再也没有别的数属于M。
算法分析：用数组存放Ｍ。对任一自然数Ｋ，若Ｋ能用Ｍ中已存在的数生成，则将Ｋ存人数组。如此依次考察自然数，则得到的必是最小的、互异的数。下面是一种实现方案：
#include<stdio.h>
int main()
{
int a[100],k,x2,x3;
a[1] = 1; x2 = 1; x3 = 1;
for(k = 2; k <= 100; k++)
if(2 * a[x2] == 3 * a[x3])
{
a[k] = 2 * a[x2++]+1; x3++;
}
else if(2 * a[x2] < 3 * a[x3])
a[k] = 2 * a[x2++]+1;
else a[k] = 3 * a[x3++]+1;
x2 = 0;
for(k = 1; k <= 100; k++)
{
printf("%4d",a[k]); ++x2;
if(x2 % 10==0) printf("\n");
}
}
另一种实现方案：
#include<stdio.h>
int main()
{
int j,m[100],y,z;
m[0] = j = 1;
y = z = 0;
while(j < 100)
{
if(m[z] * 3 >= m[y] * 2)
{
m[j] = m[y++] * 2+1;
if(m[z] * 3+1 == m[j]) z++;
}
else m[j] = m[z++] * 3+1;
j++;
}
for(j = 0; j < 100; j++)
{
printf("%6d",m[j]);
if((j + 1) % 10 == 0) printf("\n");
}
return 0;
}
6.13有一个已按升序排列的数组，现插入一个数number，要求插入后该数组仍为升序。
算法分析：这个问题可以分解为以下四步：
（1）生成一个有n个元素的有序数组a；
（2）定位插入点，设其为i；
（3）将a[i]，a[i+1]，…，a[n-1]顺序右移一位；
（4）插入新元素。
注意到插入点不外乎三种情况之一：首元素之前；末元素之后；任意两元素之间。下面就是按以上思路的一个实现方案。
#include<stdio.h>
#define MAX 50
int main()
{
int n,i,number,index,a[MAX];
/* 生成一个有n个元素的有序数组a */
printf("Input n(n<=%d)",MAX);
scanf("%d",&n);
printf("Input %d numbers to be sorted:\n",n);
for(i=0;i<=n-1;i++)
scanf("%d",&a[i]);
printf("Input the number," );
scanf("%d",&number); /* 输入欲插入的元素 */
/* 定位插入点 */
if(number >= a[n-1])
index = n; /* 插在最后 */
else if(number <= a[0])
index = 0; /* 插在最后 */
else{ /* 插在任意两元素之间 */
index = 1;
while(number > a[index])
index++;
}
/* 元素右移一位 */
for(i = n-1; i >= index; --i)
a[i+1] = a[i];
a[index]=number; /* 插入新元素 */
/* 输出插入后的结果 */
printf("sorted array are:\n");
for( i = 0; i <= n; i++)
printf("%4d",a[i]);
printf("\n");
return 0;
}
6.14 输入一正整数N(N不超过80位)，去掉其中任意S个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输出应包括所去掉的数字的位置和组成的新数。
例如,N=’178543’,S=4，删数过程如下：
178543 → 17543 → 1543 → 143 → 13
算法分析：因为N<=80，所以以字串形式输入N，使用尽可能逼近目标的贪心法来逐一删去其中S个数符，每一步总是选择一个使剩下的数最小的数符删去。之所以作出这样贪心的选择，是因为删S个数符的全局最优解，包含了删一个数符的子问题的最优解。
为了保证删1个数符后的数最小，我们按高位→低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首字符，这样形成一个新数串。然后回到串首，重复上述规则，剩下一数符……依此类推，直到删除S个数符为止。程序如下：
#include <stdio.h>
#include <string.h>
int main()
{
char a[81],c[81];
int b[80];
int len,len1,s,s1,t,k,i,j;
printf("Input the number N:");
scanf("%s",a);
printf("The wish deletes numbers,");
scanf("%d",&s);
len = len1 = strlen(a);
t = 0; s1 = s;
for(i = 0; i<len; i++)
c[i] = a[i];
for(i = 0; i < len-1; i++)
{
k = i;
for(j = i+1; j < len; j++)
if(c[j] > c[k]) k = j;
c[k] = 0;
b[t++] = k;
}
while(s)
{
k=0;
for(i = 0; i < len; i++)
if(a[i+1] > a[k]) k = i+1;
for(i = k; i < len; i++)
a[i] = a[i+1];
--len;
--s;
}
printf("\nThe new number is ");
for(i=0;i<len1-s1;i++)
printf("%c",a[i]);
printf("\n\n");
printf("There are position of to be deleted digital:");
for(i = 0; i < s1; i++)
printf("%d,",b[i]);
printf("\b%c\n ",' ');
return 0;
}
6.15 用选择法对数组中n个整数按由小到大排序。
算法分析：有多种选择排序法，教材P.135详细讨论了简单选择排序法。下面就是根据该方法编写的一个程序。
#include<stdio.h>
#define MAX 50
int main()
{
int size,i,j,k,temp,a[MAX];
printf("Input size(size<=%d),",MAX); scanf("%d",&size);
printf("Input %d numbers to be sorted:\n",size);
for(i = 0; i <= size-1; i++)
scanf("%d",&a[i]);
for(i = 0; i < size-1; i++)
{
k = i;
for(j = i+1; j < size; j++)
if(a[j] < a[k]) k = j;
if(k != i)
{
temp = a[k];
a[k] = a[i];
a[i] = temp;
}
}
printf("sorted array are:\n");
for(i = 0; i < size; i++)
printf("%d,",a[i]);
printf("\b%c\n",' ');
return 0;
}
另一种实现方案：
#include<stdio.h>
#define MAX 50
void selsort(int a[],int n)
{
int i,j,t;
for(j = 0; j < n/2; j++)
for(i = j+1; i < n-j; i++)
{
if(a[j] > a[n-j-1]) t = a[j],a[j] = a[n-1-j],a[n-1-j] = t;
if(a[i] < a[j]) t = a[j],a[j] = a[i],a[i] = t;
if(a[i] > a[n-1-j]) t = a[n-j-1],a[n-j-1] = a[i],a[i] = t;
}
}
int main()
{
int i,a[MAX],n,t;
printf("Input n(n<=%d),",MAX "); scanf("%d",&n);
printf("Input %d numbers to be sorted:\n",n);
for(i = 0; i < n; i++)
scanf("%d",&a[i]);
selsort(a,n);
printf("sorted array are:\n");
for(i = 0; i < n; i++)
printf("%d,",a[i]);
printf("\b%c\n",' ');
return 0;
}
6.16 改写例5-7，用数组实现。
算法分析：我国政府目前使用下面这些规则计算每个公民的个人月收入所得税：
含税级距X 税率（%） 速算扣除数
X≤500 5 0
500＜X≤2000 10 25
2000＜X≤5000 15 125
5000＜X≤20000 20 375
20000＜X≤40000 25 1375
40000＜X≤60000 30 3375
60000＜X≤80000 35 6375
80000＜X≤100000 40 10375
X＞100000 45 15375
例如，某公民月税前收入为4679.47元，用速算扣除法计算应纳税额为：
（4679.47-1600）*15%－125＝336.92元在例5-7中采用CASE语句设计计税器时，程序很复杂。在这里，我们改用数组来实现，计税器的设计变得很简单。下面是它的一个实现方案，其算法一目了然。
#include<stdio.h>
#include<float.h>
int main()
{
float income;
int i;
float income_limits[]
={0,500,2000,5000,20000,40000,60000,80000,100000,FLT_MAX};
float rate[] = {0,.05,.1,.15,.2,.25,.3,.35,.4,.45};
int deduction_amout[] = {0,0,24,125,375,1375,3375,6375,10375,15375};
printf("Input each month of income,");
scanf("%f",&income);
income = income - 1600.0;
for(i = 0; income > income_limits[i]; i++);
printf("tax = %f\n",income*rate[i]-deduction_amout[i]);
}
6.17 求车速。一辆以固定速度行驶的汽车，司机在上午10点看到里程表上的读数是一个对称数(即这个数从左向右读和从右向左读是完全一样的)，为95859。两小时后里程表上出现了一个新的对称数。问该车的速度是多少？新的对称数是多少？
算法分析：根据题意，设所求对称数为x，其初值为95589，对其依次递增取值，将x值的每一位分解后与其对称位置上的数进行比较，若每个对称位置上的数皆相等，则可判定x即为所求的对称数。
#include<stdio.h>
int main()
{
int t,a[5]; /* 数组a存放分解的数字位 */
long int k,x;
for(x = 95860;; x++)
{
for(t = 0,k = 100000;k >= 10;t++) /* 从高到低分解所取x值的每位*/
{/* 数字，依次存放于a[0]~a[5]中 */
a[t] = (x%k)/(k/10);
k /= 10;
}
if((a[0] == a[4]) && (a[1] == a[3]))
{
printf("The new symmetrical number kelometers is,");
printf("%d%d%d%d%d\n",a[0],a[1],a[2],a[3],a[4]);
printf("The velocity of the car is,%.2f\n",(x-95859)/2.0);
break;
}
}
}
6.18 找出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
┆
4 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 15
int main()
{
int i,a[15],j,k,m,n;
printf("Input n = "); scanf("%d",&n);
printf("Input m = "); scanf("%d",&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);
}
return 0;
}
第二种实现方案：
#include <stdio.h>
#define M 10
int a[M],m,n;
void change(int d)
{
if(a[d] != n-m+d)
a[d]++;
else{
change(d-1);
a[d] = a[d-1]+1;
}
} /* change */
int main()
{
int k;
printf("Input n\n"); scanf("%d",&n);
printf("Input m\n"); scanf("%d",&m);
for(k = 1;k <= m;k++)
a[k]=k;
do{
for(k = 1;k <= m;k++)
printf("%d",a[k]);
putchar('\n');
if(a[1] == n-m+1) break;
change(m);
}while(1);
return 0;
}
6.19 设有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);
}
