- C语言程序开发范例宝典（软件工程师典藏版）
- 杨丽 郭锐 陈雪峰编著
- 103字
- 2020-06-27 10:54:43
第4章 算法
4.1 简单问题算法
C语言的功能很强大，可以做许多复杂的编程，如编写操作系统，当然对于初学者也可以用C语言来解决一些简单的问题，本节就介绍了几个可以用C语言解决的不太复杂的问题。
实例111 任意次方后的最后三位
本实例是一个人性化的实例
实例位置：光盘\mingrisoft\04\111
实例说明
编程求一个整数任意次方后的最后三位数，即求xy的最后三位数，x和y的值由键盘输入，运行结果如图4.1所示。
图4.1 任意次方后的最后三位
技术要点
本实例的算法思想如下：题中要求一个数的任意次方，那我们首先就要考虑到计算的结果是否越界问题，如何避免产生越界问题同时又不使结果产生误差，这里在求y次方的时候每乘一次都取其后三位，这样就不会出现越界问题又可完成题目要求。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include<stdio.h>
（3）求一个数任意次方的后三位，这里采用取余的方法。
（4）主函数程序代码：
main（）
{
int i, x, y, z = 1;
printf（"please input two numbers x and y（x^y）:\n"）;
scanf（"%d%d",&x,&y）; /*输入底数和幂数*/
for（i = 1; i <= y; i++）
z=z*x % 1000; /*计算一个数任意次方的后三位*/
printf（"the last 3 digits of %d^%d is:%d\n",x,y,z）;/*输出最终结果*/
}
举一反三
根据本实例，读者可以：
编程求任意两个数相乘所得的积的最后四位。
编程求任意两个数相乘所得的积，如果是偶数则输出最后3位，如果是奇数则输出最后1位。
实例112 计算π的近似值
本实例是一个提高基础技能的程序
实例位置：光盘\mingrisoft\04\112
实例说明
根据以下公式求x的值（要求从键盘中输入精度，即某项小于输入的数值时停止迭代）：x/2=1+1/3+1×2/3×5+1×2×3/3×5×7+1×2×3×4/3×5×7× 9+…+1×2×3×…×n/3×5×7×（2n+1）程序运行后，当输入的精度为10-5时，屏幕中程序输出结果为3.14…运行结果如图4.2所示。
图4.2 计算π的近似值
技术要点
解决本题的关键是分析出各个多项式之间有着怎样的变化规律，如果这里设前一项为s，那么后一项就表示成s×n/（2×n+1），这里的n代表项数，设1为第1项，那么1/3就为第二项，依此类推，我们就能求出每一项，将每一项累加求和，就求出了最终结果。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件、进行宏定义及数据类型的指定：
#include <stdio.h>
#include<math.h>
（3）自定义fun（）函数，实现求π的近似值，代码如下：
double fun（double eps）/*自定义函数fun，用来求多项式的和*/
{
float n, t, pi, s;
t = 1;
pi = 0;
n = 1.0;
s = 1.0;
while（（fabs（s））>=eps） /*当s的绝对值小于输入的精度，执行循环体语句*/
{
pi=pi+s; /*累加求和*/
t = n /（2 *n + 1）;
s *= t;
n++;
}
pi = pi * 2;
return pi; /*将π的近似值返回*/
}
（4）主函数代码如下：
main（）
{
float n, result;
printf（"please input precision:\n"）;
scanf（"%f",&n）; /*输入精度*/
result=fun（n）; /*调用函数fun*/
printf（"the approximation of pi is %f",result）; /*将π的近似值输出*/
}
举一反三
根据本实例，读者可以编程解决如下问题：
有一分数序列：2/1、3/2、5/3、8/5、13/8、21/13……求出这个数列的前10项之和。
给一个不多于5位的正整数，输出该数的最后三位，并将该数逆序输出。
实例113 小于500的所有勾股数
本实例是一个人性化的实例
实例位置：光盘\mingrisoft\04\113
实例说明
编程求出小于500的所有勾股数并以每行显示四组勾股数的形式显示在屏幕上，运行结果如图4.3所示。
图4.3 后15行勾股数
技术要点
满足i2+j2=k2，称i、j、k为一组勾股数，它们可以构成直角三角形的三边。
当I≤j<k，
则i2+i2=2i2≤i2+j2<k2≤5002，
即可推出i<360，
因此采用三重循环逐个探测便可求出500以内的所有勾股数。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件stdio.h：
#include<stdio.h>
（3）采用三重for循环，在指定范围内逐个探测便可求出500以内的所有勾股数。
（4）主要程序代码如下：
main（）
{
long i, j, k, n = 0;
for（i = 1; i < 360; i++）
/*i在1到360之间进行穷举*/
for（j = i; j < 500; j++）
for（k = j + 1; k <= 500; k++）
if（i *i + j * j = = k *k）
/*判断这三个数是否是勾股数*/
{
printf（"%3ld^2+%3ld^2=%3ld^2 ",i,j,k）;/*将勾股数按指定格式输出*/
n++;
if（n % 4 = = 0）
/*没输出4个进行换行*/
printf（"\n"）;
}
}
举一反三
根据本实例，读者可以：
编程输出10～20的所有整数的平方值。
输出100以内的所有偶数。
实例114 能否组成三角形
本实例是一个人性化的实例
实例位置：光盘\mingrisoft\04\114
实例说明
以下程序根据输入的三角形的三边判断是否能组成三角形，若可以则输出它的面积和三角形的类型。运行结果如图4.4所示。
图4.4 能否组成三角形
技术要点
做本实例之前必须知道三角形的一些相关内容，例如如何判断输入的三边是否能组成三角形、三角形面积的求法等，当从键盘中输入三边，只需判断这三条边中任意的两边之和是否大于第三边，如果大于再做进一步判断该三角形是什么三角形，否则说明不能组成三角形。
实例中要注意“&&”和“||”的恰当使用。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <math.h>
（3）从键盘中输入三角形的三边，判断其两边之和是否大于第三边，若大于则进一步判断该三角形是什么三角形，否则输入的三边不能组成三角形。
（4）主函数程序代码如下：
main（）
{
float a, b, c;
float s, area;
scanf（"%f,%f,%f", &a, &b, &c）; /*输入三条边*/
if（a+b>c&&b+c>a&&a+c>b） /*判断两边之和是否大于第三边*/
{
s =（a + b + c）/ 2;
area=sqrt（s*（s-a）*（s-b）*（s-c））; /*计算三角形的面积*/
printf（"the area is:%f\n",area）; /*输出三角形的面积*/
if（a==b&&a==c） /*判断三条边是否相等*/
printf（"equilateral triangle\n"）;
/*输出等边三角形*/
else if（a = = b || a = = c || b = = c）
/*判断三角形中是否有两边相等*/
printf（"isoceles triangle\n"）;
/*输出等腰三角形*/
else if（（a *a + b * b = = c *c）||（a *a + c * c = = b *b）||（b *b + c
* c = = a *a））
/*判断是否有两边的平方和大于第三边的平方*/
printf（"right angled triangle\n"）;
/*输出直角三角形*/
else
printf（"triangle"）;
/*普通三角形*/
}
else
printf（"can not compose triangle"）;
/*如果两边之和小于第三边不能组成三角形*/
}
举一反三
根据本实例，读者可以：
从键盘中输入平行四边形的两边，编程求其周长及面积。
从键盘中输入圆的半径，编程求其周长及面积。
实例115 偶数拆分
本实例是一个人性化的实例
实例位置：光盘\mingrisoft\04\115
实例说明
从键盘中输入一个偶数，编程实现将该偶数拆分成两个素数之和并输出在屏幕上。运行结果如图4.5所示。
图4.5 偶数拆分
技术要点
本实例的算法思想如下：要将偶数a分成b和c两部分，首先将b从3开始到a/2进行逐个探测，如若b是素数，则c=a−b，再对c做判断，如果c是素数，则b和c就满足题意，如有一个数不是素数则进行下次探测。设置flag用来标志这个偶数是否能够拆分成两个素数，如果不能以便给出提示信息。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
#include <math.h>
（3）利用算数运算符判断b和c是否都是素数，如果都是素数，则满足题中条件将其输出。
（4）主函数程序代码如下：
main（）
{
int a, b, c, d, flag = 0;
scanf（"%d",&a）; /*从键盘中输入一个偶数*/
for（b=3;b<=a/2;b+=2） /*因为拆分成素数，所以b每次加2*/
{
for（c=2;c<=sqrt（b）;c++） /*判断b是否是素数*/
if（b % c = = 0）
break;
if（c > sqrt（b））
d=a-b; /*如果b是素数求出d*/
else
continue;
for（c=2;c<=sqrt（d）;c++） /*判断d是否是素数*/
if（d % c = = 0）
break;
if（c > sqrt（d））
{
printf（"the result is:%d=%d+%d\n",a,b,d）; /*将拆分的结果输出*/
flag=1; /*flag置1说明至少可拆分成一组*/
}
}
if（flag = = 0）
printf（"can not split!"）;
}
举一反三
根据本实例，读者可以：
求10～100的数n，该数等于3个连续数相乘的积。
找出5个奇数，要求该奇数等于两个素数的积。
实例116 乘积大于和的数
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\04\116
实例说明
编程求10～100满足每位上数的乘积大于每位上数和的所有数，并将结果以每行5个的形式输出。运行结果如图4.6所示。
技术要点
本实例的算法思想如下：利用算术运算符“%”和“/”来分离这个两位数，将分离出的数分别求积与求和，再对求出的积与和进行判断，看积是否大于和，如果积大于和则将该数输出，否则进行下次循环。
图4.6 乘积大于和的数
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include<stdio.h>
（3）利用for语句对10到100之间的数进行逐个探测，求出各位的和与积之后，对满足条件的数据输出。
（4）主函数程序代码如下：
main（）
{
int n,k=1,s=0,m,c= -1;
printf（"the result is:\n"）;
for（n = 11; n < 100; n++）
{
k=1; /*存储各位数之积*/
s=0; /*存储各位数之和*/
m = n;
while（m）
{
k*=m % 10; /*分离出各位求积*/
s+=m % 10; /*分离出各位求和*/
m /= 10;
}
if（k>s） /*判断积是否大于和*/
{
c++; /*统计个数*/
if（c % 5==0） /*5个一换行*/
printf（"\n"）;
printf（"%5d", n）;
}
}
}
举一反三
根据本实例，读者可以：
输入两个数，如果这两个数的和是回文数，则求这两个数的积，否则求差。
编程计算高次方的尾数。
实例117 求各位上和为5的数
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\04\117
实例说明
编程求100～10000满足各位数字之和是5的所有数。以5个数字一行的形式输出。运行结果如图4.7所示。
图4.7 求各位上和为5的数
技术要点
本实例的算法思想如下：定义一个变量s用来存储各位之和，s的初始值应为0，将遍历到的数值各位进行分离求和，各位分离同样用到了算术运算符“%”和“/”。对求出的和做判断，满足条件的输出，不满足条件的结束本次循环继续下次循环。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include<stdio.h>
（3）用变量s存储各位之和，count来记录元素个数，因为从0开始计数，所以输出时count值要加1。
（4）主函数程序代码如下：
main（）
{
int i,s,k,count= -1;
for（i=100;i<=1000;i++） /*对100～1000的数进行穷举*/
{
s=0; /*s用来存储各位之和*/
k = i;
while（k）
{
s=s+k % 10; /*求各位之和*/
k=k/10; /*分离出各位*/
}
if（s!=5） /*判断和是否等于5*/
continue; /*结束本次循环继续下次循环*/
else
{
count++; /*计数器*/
if（count % 5==0） /*输出5个数据进行换行*/
printf（"\n"）;
printf（"%5d", i）;
}
}
printf（"\ntotal is %d",count+1）; /*输出满足条件的数据个数*/
}
举一反三
根据本实例，读者可以：
求100～1000各位乘积是24的所有数。
求100～1000各位数字均是奇数且各位数字之和也是奇数的数。
实例118 计算某日是该年第几天
本实例是一个人性化的实例
实例位置：光盘\mingrisoft\04\118
实例说明
本实例要求编写一个计算天数的程序，即从键盘中输入年、月、日，在屏幕中输出此日期是该年的第几天。运行结果如图4.8所示。
图4.8 计算某日是该年第几天
技术要点
要实现本实例要求的功能主要有以下两个技术要点。
第一，判断输入的年份是否是闰年，这里我们自定义函数leap来进行判断。该函数的核心内容就是闰年的判断条件即能被4整除但不能被100整除，或能被400整除。
第二，如何求此日期是该年的第几天。这里将12个月每月的天数存到数组中，因为闰年2月份的天数有别于平年，故采用两个数组a和b分别存储。当输入年份是平年，月份为m时求出平年的前m−1个月天数的累加和。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）自定义leap（）函数实现判断输入的年份是否为闰年，代码如下：
int leap（int a） /*自定义函数leap用来指定年份是否为闰年*/
{
if（a % 4==0&&a % 100!=0||a % 400==0） /*闰年判定条件*/
return 1; /*是闰年返回1*/
else
return 0; /*不是闰年返回0*/
}
（4）自定义number（）函数实现计算输入的日期为该年的第几天，代码如下：
int number（int year, int m, int d）/*自定义函数number计算输入日期为该年第几天*/
{
int sum = 0, i, j, k, a[12] =
{
31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
}; /*数组a存放平年每月的天数*/
int b[12] =
{
31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
}; /*数组b存放闰年每月的天数*/
if（leap（year）==1） /*判断是否为闰年*/
for（i = 0; i < m -1; i++）
sum+=b[i]; /*是闰年，累加数组b前m-1个月份天数*/
else
for（i = 0; i < m -1; i++）
sum+=a[i]; /*不是闰年，累加数组a前m-1个月份天数*/
sum+=d; /*将前面累加的结果加上日期，求出总天数*/
return sum; /*将计算的天数返回*/
}
（5）main（）函数作为程序的入口函数，代码如下：
main（）
{
int year,month,day,n; /*定义变量为基本整型*/
printf（"please input year,month,day\n"）;
scanf（"%d%d%d",&year,&month,&day）; /*输入年月日*/
n=number（year,month,day）; /*调用函数number*/
printf（"di %d tian\n", n）;
}
举一反三
根据本实例，读者可以：
输入某日计算该日是从1990年开始的第几天。
如果2008年8月15日是星期五，编程实现输入该日期后的某日，输出该日期是星期几。
4.2 排序算法
排序是数据处理中的一种重要运算。在当今的计算机系统中，在数据排序上花费的时间占用了一部分系统运行时间，因此，研究和采用一些好的排序算法，对于提高工作效率是很重要的。本节就介绍了几种常见的排序算法。
实例119 直接插入排序
本实例可以方便操作、提高效率
实例位置：光盘\mingrisoft\04\119
实例说明
插入排序是把一个记录插入到已排序的有序序列中去，使整个序列在插入了该记录后仍然有序。插入排序中较简单的一种方法便是直接插入排序，它插入位置的确定是通过将待插入的记录与有序区中的各记录自右向左依次比较其关键字值大小来确定的。本实例要求使用直接插入排序法将如下数字由小到大进行排序，数字分别为：25、12、36、45、2、9、39、22、98、37。运行结果如图4.9所示。
图4.9 直接插入排序
技术要点
本实例算法过程如下。
原始顺序：25 12 36 45 2 9 39 22 98 37
注意：本算法中使用了监视哨，主要是为了避免数据在后移时丢失。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）自定义isort（）函数实现直接插入排序，代码如下：
void insort（int s[],int n） /*自定义函数isort*/
{
int i, j;
for（i=2;i<=n;i++） /*数组下标从2开始，0做监视哨，1一个数据无可比性*/
{
s[0]=s[i]; /*给监视哨赋值*/
j=i-1; /*确定要进行比较的元素的最右边位置*/
while（s[0] < s[j]）
{
s[j+1]=s[j]; /*数据右移*/
j--; /*移向左边一个未比较的数*/
}
s[j+1]=s[0]; /*在确定的位置插入s[i]*/
}
}
（4）main（）函数作为程序的入口函数，代码如下：
main（）
{
int a[11],i; /*定义数组及变量为基本整型*/
printf（"please input number:\n"）;
for（i = 1; i <= 10; i++）
scanf（"%d",&a[i]）; /*接收从键盘中输入的10个数据到数组a中*/
printf（"the original order:\n"）;
for（i = 1; i < 11; i++）
printf（"%5d",a[i]）; /*将为排序前的顺序输出*/
insort（a,10）; /*调用自定义函数isort（）*/
printf（"\nthe sorted numbers:\n"）;
for（i = 1; i < 11; i++）
printf（"%5d",a[i]）; /*将排序后的数组输出*/
printf（"\n"）;
}
举一反三
根据本实例，读者可以：
使用直接插入排序法将如下数字由小到大进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
使用直接插入排序法将如下数字由大到小进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
实例120 希尔排序
本实例可以方便操作、提高效率
实例位置：光盘\mingrisoft\04\120
实例说明
用希尔排序法对下面一组数字进行由小到大排序，数字分别为：69、56、12、136、3、55、46、99、88、25。运行结果如图4.10所示。
图4.10 希尔排序
技术要点
希尔排序是在直接插入排序的基础上的改进，也就是将要排序的序列按固定增量分成若干组，等距离者在同一组中，然后再在组内进行直接插入排序。这里面的固定增量从n/2开始，以后每次缩小到原来的一半。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）自定义shsort（）函数实现希尔排序，代码如下：
void shsort（int s[],int n） /*自定义函数shsort*/
{
int i, j, d;
d=n/2; /*确定固定增量值*/
while（d >= 1）
{
for（i=d+1;i<=n;i++） /*数组下标从d+1开始进行直接插入排序*/
{
s[0]=s[i]; /*设置监视哨*/
j=i-d; /*确定要进行比较的元素的最右边位置*/
while（（j > 0）&&（s[0] < s[j]））
{
s[j+d]=s[j]; /*数据右移*/
j=j-d; /*向左移d个位置*/
}
s[j+d]=s[0]; /*在确定的位置插入s[i]*/
}
d=d/2; /*增量变为原来的一半*/
}
}
（4）main（）函数作为程序的入口函数，代码如下：
main（）
{
int a[11],i; /*定义数组及变量为基本整型*/
printf（"please input numbers:\n"）;
for（i = 1; i <= 10; i++）
scanf（"%d",&a[i]）; /*从键盘中输入10个数据*/
shsort（a,10）; /*调用shsort（）函数*/
printf（"the sorted numbers:\n"）;
for（i = 1; i <= 10; i++）
printf（"%5d",a[i]）; /*将排好序的数组输出*/
}
举一反三
根据本实例，读者可以：
使用希尔排序法将如下数字由小到大进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
使用希尔排序法将如下数字由大到小进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
实例121 起泡排序
本实例可以方便操作、提高效率
实例位置：光盘\mingrisoft\04\121
实例说明
用起泡法对任意输入的10个数进行由小到大排序。运行结果如图4.11所示。
图4.11 起泡排序
技术要点
本实例要求用起泡法对10个数进行由小到大排序，下面就介绍起泡法的基本思路。
如果要对n个数进行起泡排序，那么要进行n−1趟比较，在第1趟比较中要进行n−1次两两比较，在第j趟比较中要进行n−j次两两比较。从这个基本思路中我们也会发现趟数决定了两两比较的次数，这样我们就很容易将两个for循环联系起来了。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）通过两个for循环实现起泡排序的全过程，外层for循环决定冒泡排序的趟数，内层for循环决定每趟所进行两两比较的次数。
（4）主要程序代码如下：
main（）
{
int i,j,t,a[11]; /*定义变量及数组为基本整型*/
printf（"please input 10 numbers:\n"）;
for（i = 1; i < 11; i++）
scanf（"%d",&a[i]）; /*从键盘中输入10个数*/
for（i=1;i<10;i++） /*变量i代表比较的趟数*/
for（j=1;j<11-i;j++） /*变量j代表每趟两两比较的次数*/
if（a[j] > a[j + 1]）
{
t=a[j]; /*利用中间变量实现俩值互换*/
a[j] = a[j + 1];
a[j + 1] = t;
}
printf（"the sorted numbers:\n"）;
for（i = 1; i <= 10; i++）
printf（"%5d",a[i]）; /*将冒泡排序后的顺序输出*/
}
举一反三
根据本实例，读者可以：
使用起泡排序法将如下数字由小到大进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
使用起泡排序法将如下数字由大到小进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
实例122 快速排序
本实例可以方便操作、提高效率
实例位置：光盘\mingrisoft\04\122
实例说明
用快速排序法对以下数据进行由小到大排序，数据分别为：99、45、12、36、69、22、62、796、4、696。运行结果如图4.12所示。
图4.12 快速排序
技术要点
快速排序是起泡排序的一种改进，主要的算法思想是在待排序的n个数据中取第一个数据作为基准值，将所有的记录分为3组，使得第一组中各数据值均小于或等于基准值，第二组便是做基准值的数据，第三组中各数据值均大于或等于基准值。这便实现了第一趟分割，然后再对第一组和第三组分别重复上述方法，依此类推，知道每组中只有一个记录为止。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）自定义qusort（）函数实现希尔排序，代码如下：
void qusort（int s[],int start,int end） /*自定义函数qusort（）*/
{
int i,j; /*定义变量为基本整型*/
i=start; /*将每组首个元素赋给i*/
j=end; /*将每组末尾元素赋给j*/
s[0]=s[start]; /*设置基准值*/
while（i < j）
{
while（i < j && s[0] < s[j]）
j--; /*位置左移*/
if（i < j）
{
s[i]=s[j]; /*将s[j]放到s[i]的位置上*/
i++; /*位置右移*/
}
while（i < j && s[i] <= s[0]）
i++; /*位置右移*/
if（i < j）
{
s[j]=s[i]; /*将大于基准值的s[j]放到s[i]位置*/
j--; /*位置右移*/
}
}
s[i]=s[0]; /*将基准值放入指定位置*/
if（start < i）
qusort（s,start,j-1）; /*对分割出的部分递归调用函数qusort（）*/
if（i < end）
qusort（s, j + 1, end）;
}
（4）main（）函数作为程序的入口函数，代码如下：
main（）
{
int a[11],i; /*定义数组及变量为基本整型*/
printf（"please input numbers:\n"）;
for（i = 1; i <= 10; i++）
scanf（"%d",&a[i]）; /*从键盘中输入10个要进行排序的数*/
qusort（a,1,10）; /*调用qusort（）函数进行排序*/
printf（"the sorted numbers:\n"）;
for（i = 1; i <= 10; i++）
printf（"%5d",a[i]）; /*输出排好序的数组*/
}
举一反三
根据本实例，读者可以：
使用快速排序法将如下数字由小到大进行排序，数字分别为：45，68、12、32、7、85、456、258、123、357。
使用快速排序法将如下数字由大到小进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
实例123 选择排序
本实例可以方便操作、提高效率
实例位置：光盘\mingrisoft\04\123
实例说明
用选择排序法对以下数据进行由小到大排序，数据分别为：526、36、2、369、56、45、78、92、125、52。运行结果如图4.13所示。
图4.13 选择排序
技术要点
选择排序的基本算法是从待排序的区间中经过选择和交换后选出最小的数值存放到a[0]中，再从剩余的未排序区间中将经过选择和交换后选出的最小数值存放到a[1]中，a[1]中的数字仅小于a[0]，依此类推，即可实现排序。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）程序中用到两个for循环语句，第一个for循环是确定位置的，该位置是存放每次从待排序数列中经选择和交换后所选出的最小数。第二个for循环是实现将确定位置上的数与后面待排序区间中的数进行比较的。
（4）主要程序代码如下：
main（）
{
int i,j,t,a[11]; /*定义变量及数组为基本整型*/
printf（"please input 10 numbers:\n"）;
for（i = 1; i < 11; i++）
scanf（"%d",&a[i]）; /*从键盘中输入要排序的10个数字*/
for（i = 1; i <= 9; i++）
for（j = i + 1; j <= 10; j++）
if（a[i]>a[j]） /*如果后一个数比前一个数大则利用中间变量t实现俩值互换*/
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
printf（"the sorted numbers:\n"）;
for（i = 1; i <= 10; i++）
printf（"%5d",a[i]）; /*将排好序的数组输出*/
}
举一反三
根据本实例，读者可以：
使用选择排序法将如下数字由小到大进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
使用选择排序法将如下数字由大到小进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
实例124 归并排序
本实例可以方便操作、提高效率
实例位置：光盘\mingrisoft\04\124
实例说明
用归并排序法对以下数据进行由小到大排序，数据分别为：695、458、362、789、12、15、163、23、2、986。运行结果如图4.14所示。
图4.14 归并排序
技术要点
归并是将两个或多个有序记录序列合并成一个有序序列。归并方法有多种，一次对两个有序记录序列进行归并，称为二路归并排序，也有三路归并排序及多路归并排序。本实例是二路归并排序，基本方法如下。
（1）将n个记录看成是n个长度为1的有序子表。
（2）将两两相邻的有序子表进行归并。
（3）重复执行（2），直到归并成一个长度为n的有序表。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）自定义函数merge（）函数，实现一次归并排序，代码如下：
void merge（int r[], int s[], int x1, int x2, int x3）/*实现一次归并排序函数*/
{
int i, j, k;
i=x1; /*第一部分的开始位置*/
j=x2+1; /*第二部分的开始位置*/
k = x1;
while（（i <= x2）&&（j <= x3））
/*当i和j都在两个要合并的部分中*/
if（r[i] <= r[j]）
/*筛选两部分中较小的元素放到数组s中*/
{
s[k] = r[i];
i++;
k++;
}
else
{
s[k] = r[j];
j++;
k++;
}
while（i <= x2）
/*将x1～x2范围内的未比较的数顺次加到数组r中*/
s[k++] = r[i++];
while（j <= x3）
/*将x2+1～x3范围内的未比较的数顺次加到数组r中*/
s[k++] = r[j++];
}
（4）自定义merge_sort函数，实现归并排序，代码如下：
void merge_sort（int r[], int s[], int m, int n）
{
int p;
int t[20];
if（m = = n）
s[m] = r[m];
else
{
p =（m + n）/ 2;
merge_sort（r, t, m, p）;
/*递归调用merge_sort函数将r[m]～r[p]归并成有序的t[m]～t[p]*/
merge_sort（r,t,p+1,n）; /*递归调用merge_sort函数将r[p
+1] ～r[n]归并成有序的t[p+1] ～t[n]*/
merge（t,s,m,p,n）; /*调用函数将前两部分归并到s[m] ～s[n]*/
}
}
（5）主函数程序代码如下：
main（）
{
int a[11];
int i;
printf（"please input 10 numbers:\n"）;
for（i = 1; i <= 10; i++）
scanf（"%d", &a[i]）;
/*从键盘中输入10个数*/
merge_sort（a,a,1,10）; /*调用merge_sort函数进行归并排序*/
printf（"the sorted numbers:\n"）;
for（i = 1; i <= 10; i++）
printf（"%5d", a[i]）;
/*将排序后的结构输出*/
}
举一反三
根据本实例，读者可以：
使用归并排序法将如下数字由小到大进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
使用归并排序法将如下数字由大到小进行排序，数字分别为：45、68、12、32、7、85、456、258、123、357。
4.3 查找算法
查找是数据处理中使用较频繁的一种重要操作。当数据量较大时，提高各种查找算法的效率就显得十分重要，本节介绍几个较为常用的查找算法。
实例125 顺序查找
本实例可以提高查询效率
实例位置：光盘\mingrisoft\04\125
实例说明
采用顺序查找法在关键字序列25、65、356、569、55、65、45、66、154、66中查找关键字为154的元素。运行结果如图4.15所示。
图4.15 顺序查找
技术要点
本例顺序查找的算法思想是：从数组中的第一个元素25开始，将给定的值154与数组中的元素逐个比较，直到两者相等，查到所要找的元素并输出查找次数及该元素在数组中的位置。否则输出no found表示数组中没有要找的元素。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）自定义search（）函数实现顺序查找，代码如下：
void search（int key,int a[],int n） /*自定义函数search*/
{
int i, count = 0, count1 = 0;
for（i = 0; i < n; i++）
{
count++; /*count记录查找次数*/
if（a[i]==key） /*判断要查找的关键字与数组中的元素是否相等*/
{
printf（"search %d times a[%d]=%d\n",count,i,key）; /*输出查找次数及在数组中的位置*/
count1++; /*count1记录查找成功次数*/
}
}
if（count1==0） /*判断是否查找到h*/
printf（"no found!"）; /*如果未查找到输出no found*/
}
（4）main（）函数作为程序的入口函数，代码如下：
main（）
{
int n, key, a[100], i;
printf（"please input the length of array:\n"）;
scanf（"%d",&n）; /*输入要输入的元素个数*/
printf（"please input element:\n"）;
for（i = 0; i < n; i++）
scanf（"%d",&a[i]）; /*输入元素存到数组a中*/
printf（"please input the number which do you want to search:\n"）;
scanf（"%d",&key）; /*指定要查找的元素*/
search（key,a,n）; /*调用自定义的search函数*/
}
举一反三
根据本实例，读者可以：
采用顺序查找法在关键字序列45、85、63、785、42、654、219、146、325、795中查找关键字为146的元素。
采用顺序查找法在关键字序列45、85、63、785、42、654、219、146、325、795中查找关键字为111的元素。
实例126 二分查找
本实例可以提高查询效率
实例位置：光盘\mingrisoft\04\126
实例说明
采用二分查找法在有序表11、13、18、28、39、56、69、89、98、122中查找关键字为89的元素。运行结果如图4.16所示。
图4.16 顺序查找
技术要点
二分查找就是常说的折半查找，其基本思想是：首先选取表中间位置的记录，将其关键字与给定关键字key进行比较，若相等，则查找成功；若key值比该关键字值大，则要找的元素一定在右子表中，继续对右子表进行折半查找；若key值比该关键字值小，则要找的元素一定在左子表中，继续对左子表进行折半查找。如此递推，直到查找成功或查找失败（查找范围为0）。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）自定义binary_search（）函数实现二分查找，代码如下：
void binary_search（int key, int a[], int n）/*自定义函数binary_search*/
{
int low, high, mid, count = 0, count1 = 0;
low = 0;
high = n -1;
while（low<high） /*当查找范围不为0时执行循环体语句*/
{
count++; /*count记录查找次数*/
mid=（low+high）/2; /*求出中间位置*/
if（key<a[mid]） /*当key小于中间值*/
high=mid-1; /*确定左子表范围*/
else if（key>a[mid]） /*当key大于中间值*/
low=mid+1; /*确定右子表范围*/
else if（key==a[mid]） /*当key等于中间值证明查找成功*/
{
printf（"success!\nsearch %d times!a[%d]=%d", count, mid, key）;
/*输出查找次数及所查找元素在数组中的位置*/
count1++; /*count1记录查找成功次数*/
break;
}
}
if（count1==0） /*判断是否查找失败*/
printf（"no found!"）; /*查找失败输出no found*/
}
（4）main（）函数作为程序的入口函数，代码如下：
main（）
{
int i, key, a[100], n;
printf（"please input the length of array:\n"）;
scanf（"%d",&n）; /*输入数组元素个数*/
printf（"please input the element:\n"）;
for（i = 0; i < n; i++）
scanf（"%d",&a[i]）; /*输入有序数列到数组a中*/
printf（"please input the number which do you want to search:\n"）;
scanf（"%d",&key）; /*输入要查找的关键字*/
binary_search（key,a,n）; /*调用自定义函数*/
}
举一反三
根据本实例，读者可以：
采用二分查找法在关键字序列45、85、63、785、42、654、219、146、325、795中查找关键字为146的元素。
采用二分查找法在关键字序列45、85、63、785、42、654、219、146、325、795中查找关键字为111的元素。
实例127 分块查找
本实例可以提高查询效率
实例位置：光盘\mingrisoft\04\127
实例说明
采用分块查找法在有序表11、13、18、28、39、56、69、89、98、122、135、146、156、256、289中查找关键字为89的元素。运行结果如图4.17所示。
图4.17 分块查找
技术要点
分块查找也称为索引顺序查找，要求将待查的元素均匀地分成块，块间按大小排序，块内不排序，所以要建立一个块的最大（或最小）关键字表，称为索引表。
本实例中将给出的15个数按关键字大小分成了3块，这15数的排列是一个有序序列，也可以给出无序序列，但是也必须得满足分在第一块中的任意数都小于第二块中的所有数，第二块中的所有数都小于第三块中的所有数。当要查找关键字为key的元素时，则先用顺序查找在已建好的索引表中查出key所在的块中，再在对应的块中顺序查找key，若key存在则输出其相应位置，否则输出提示信息。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）定义结构体index，用于存储块的结构，并定义该结构体数组index_table。代码如下：
struct index /*定义块的结构*/
{
int key;
int start;
int end;
}index_table[4]; /*定义结构体数组*/
（4）自定义block_search（）函数，实现分块查找，代码如下：
int block_search（int key,int a[]） /*自定义实现分块查找*/
{
int i, j;
i = 1;
while（i<=3&&key>index_table[i].key） /*确定在那个块中*/
i++;
if（i>3） /*大于分得的块数，则返回0*/
return 0;
j=index_table[i].start; /*j等于块范围的起始值*/
while（j<=index_table[i].end&&a[j]!=key） /*在确定的块内进行查找*/
j++;
if（j>index_table[i].end） /*如果大于块范围的结束值，则说明没有要查找的数,j置0*/
j = 0;
return j;
}
（5）main（）函数作为程序的入口函数，代码如下：
main（）
{
int i, j = 0, k, key, a[16];
printf（"please input the number:\n"）;
for（i = 1; i < 16; i++）
scanf（"%d",&a[i]）; /*输入由小到大的15个数*/
for（i = 1; i <= 3; i++）
{
index_table[i].start=j+1; /*确定每个块范围的起始值*/
j = j + 1;
index_table[i].end=j+4; /*确定每个块范围的结束值*/
j = j + 4;
index_table[i].key=a[j]; /*确定每个块范围中元素的最大值*/
}
printf（"please input the number which do you want to search:\n"）;
scanf（"%d",&key）; /*输入要查询的数值*/
k=block_search（key,a）; /*调用函数进行查找*/
if（k != 0）
printf（"success.the position is:%d\n",k）;/*如果找到该数，则输出其位置*/
else
printf（"no found!"）; /*若未找到则输出提示信息*/
}
举一反三
根据本实例，读者可以：
采用分块查找法在关键字序列45、85、63、785、42、654、219、146、325、795中查找关键字为146的元素。
采用分块查找法在关键字序列45、85、63、785、42、654、219、146、325、795中查找关键字为111的元素。
实例128 哈希查找
本实例可以提高查询效率
实例位置：光盘\mingrisoft\04\128
实例说明
编程实现哈希查找，要求如下：已知哈希表长度为11，哈希函数为H（key）=key%11，随机产生待散列的小于50的8个元素，同时采用线性探测再散列的方法处理冲突，任意输入要查找的数据，无论找到与否均给出提示信息。运行结果如图4.18所示。
图4.18 哈希查找
技术要点
哈希函数的构造方法常用的有5种，分别是数字分析法、平方取中法、分段叠加、伪随机数法和余数法，这里面余数法比较常用。因为本实例中已给出哈希函数所以不必构造，直接按照题中给的哈希函数来运算便可。
虽然通过构造好的哈希函数可以减少冲突，但是冲突是不可能完全避免的，所以就相应地产生了避免哈希冲突常用的4种方法，分别如下。
1.开放定址法
● 线性探测再散列
● 二次探测再散列
2.链地址法
3.再哈希法
4.建立公共溢出区
开放定址法中的线性探测再散列比较常用，该方法的特点是冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件、进行宏定义并声明全局变量：
#include <stdio.h>
#include <time.h>
#define Max 11
#define N 8
int hashtable[Max];
（3）自定义func（）函数，用于哈希函数的值。代码如下：
int func（int value）
{
return value % Max; /*哈希函数*/
}
（4）自定义search（）函数，实现哈希查找，代码如下：
int search（int key） /*自定义函数实现哈希查询*/
{
int pos, t;
pos=func（key）; /*哈希函数确定出的位置*/
t=pos; /*t存放确定出的位置*/
while（hashtable[t]!=key&&hashtable[t]!= -1）
/*如果该位置上不等于要查找的关键字且不为空*/
{
t=（t+1）% Max; /*利用线性探测求出下一个位置*/
if（pos = = t）
/*如果经多次探测又回到原来用哈希函数求出的位置则说明要查找的数不存在*/
return -1;
}
if（hashtable[t]== -1）
/*如果探测的位置是-1则说明要查找的数不存在*/
return NULL;
else
return t;
}
（5）自定义creathash（）函数，实现哈希表创建，代码如下：
void creathash（int key） /*自定义函数创建哈希表*/
{
int pos, t;
pos=func（key）; /*哈希函数确定元素的位置*/
t = pos;
while（hashtable[t]!= -1）
/*如果该位置有元素存在则进行线性探测再散列*/
{
t =（t + 1）% Max;
if（pos = = t）
/*如果冲突处理后确定的位置与原位置相同则说明哈希表已满*/
{
printf（"hash table is full\n"）;
return ;
}
}
hashtable[t]=key; /*将元素放入确定的位置*/
}
（6）main（）函数作为程序的入口函数，代码如下：
main（）
{
int flag[50];
int i, j, t;
for（i = 0; i < Max; i++）
hashtable[i]= -1;
/*哈希表中初始位置全置-1*/
for（i = 0; i < 50; i++）
flag[i] = 0;
/*50以内所有数未产生时均标志为0*/
srand（（unsigned long）time（0））; /*利用系统时间做种子产生随机数*/
i = 0;
while（i != N）
{
t=rand（）% 50; /*产生一个50以内的随机数赋给t*/
if（flag[t] = = 0）
/*查看t是否产生过*/
{
creathash（t）; /*调用函数创建哈希表*/
printf（"%2d:",t）; /*将该元素输出*/
for（j = 0; j < Max; j++）
printf（"（%2d）", hashtable[j]）;
/*输出哈希表中内容*/
printf（"\n"）;
flag[t]=1; /*将产生的这个数标志为1*/
i++; /*i自加*/
}
}
printf（"please input number which do you want to search:"）;
scanf（"%d",&t）; /*输入要查找的元素*/
if（t > 0 && t < 50）
{
i=search（t）; /*调用search进行哈希查找*/
if（i!= -1）
printf（"success!The position is:%d\n", i）;
/*若查找到该元素则输出其位置*/
else
printf（"sorry,no found!"）;
/*未找到输出提示信息*/
}
else
printf（"inpput error!"）;
}
举一反三
根据本实例，读者可以：
采用哈希查找法在关键字序列45、85、63、785、42、654、219、146、325、795中查找关键字为146的元素。
采用哈希查找法在关键字序列45、85、63、785、42、654、219、146、325、795中查找关键字为111的元素。
4.4 定理与猜想
有些定理或猜想要进行验证，往往需要很大的计算量，这时如果采用编程的方法来验证定理或猜想是否正确就会节省很多时间，本小结就介绍了几个用C语言编程来验证定理或猜想的正确性。
实例129 斐波那契数列
这是一个可以提高分析能力的实例
实例位置：光盘\mingrisoft\04\129
实例说明
Fibonacci数列的特点是第1、2两个数为1、1。从第3个数开始，该数是前两个数之和。求这个数列的前30个元素。运行结果如图4.19所示。
图4.19 斐波那契
技术要点
分析题目中的要求我们可以用如下等式来表示斐波那契数列：
F1=1 （n=1）
F2=1 （n=2）
Fn=Fn-1+Fn-2 （n≥3）
这里面我们将F的下标看成数组的下标即可完成该程序。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）程序中用到两个for循环语句，第一个for循环是实现从第3项开始每一项等于前两项之和。第二个for循环是将存储在数组中的数据以5个一行的形式输出。
（4）主要程序代码如下：
main（）
{
int i; /*定义整型变量i*/
long f[31]; /*意义数组为长整形*/
f[1]=1,f[2]=1; /*数组中的f[1]、f[2]赋初值为1*/
for（i = 3; i < 31; i++）
f[i]=f[i-1]+f[i-2]; /*数列中从第3项开始每一项等于前两项之和*/
for（i = 1; i < 31; i++）
{
printf（"%10ld",f[i]）; /*输出数组中的30个元素*/
if（i % 5 = = 0）
printf（"\n"）; /*每5个元素进行一次换行*/
}
}
举一反三
根据本实例，读者可以编程实现以下问题：
从键盘中任意输入两个数，输出包括这两个数在内的20个数据，这20个数据有如下关系：输入的两个数不变，第三个数等于第二个数减第一个数，第四个数等于第三个数减去第二个数，依此类推。
从键盘中任意输入两个数，输出包括这两个数在内的10个数据，这10个数据有如下关系：输入的两个数不变，第三个数等于第二个数与第一个数的乘积再除以4，第四个数等于第三个数与第二个数的乘积再除以4，依此类推。
实例130 角谷猜想
这是一个可以提高分析能力的实例
实例位置：光盘\mingrisoft\04\130
实例说明
角谷猜想的内容是：任给一个自然数，若为偶数则除以2，若为奇数则乘3加1，得到一个新的自然数后按照上面的法则继续演算，若干次后得到的结果必然为1。编程验证该定理。运行结果如图4.20所示。
图4.20 角谷猜想
技术要点
本实例没有太多难点，只需根据题中给的条件编写程序即可，这里只强调一点就是判断一个数是奇数还是偶数，程序中采用对2取余的方法，若余数为0则说明该数是偶数，否则该数为奇数。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）程序中采用while循环来判断每次运算所得到的结果是否为1，当不为1时继续按照题中给的条件进行判断，直到最终结果等于1。
（4）主要程序代码如下：
main（）
{
long i,n; /*定义变量为长整形*/
printf（"please input a number:\n"）;
scanf（"%ld",&n）; /*从键盘中任意输入一长整形数*/
while（n!=1） /*当最终结果不为1时一直执行循环体语句*/
{
if（n % 2==0） /*判断n是否为偶数*/
{
printf（"%ld/2=%ld\n", n, n / 2）;
n=n/2; /*当n为偶数时n除以2*/
}
else
{
printf（"%ld*3+1=%ld\n", n, n *3+1）;
n=n*3+1; /*当n为奇数时乘以3加1*/
}
}
}
举一反三
根据本实例，读者可以：
求13的13次方的最后三位。
一个5位数，判断它是不是回文数。
实例131 哥德巴赫猜想
这是一个可以提高分析能力的实例
实例位置：光盘\mingrisoft\04\131
实例说明
验证100以内的正偶数都能分解为两个素数之和，即验证哥德巴赫猜想对100以内的正偶数成立。运行结果的后五行如图4.21所示。
图4.21 哥德巴赫猜想
技术要点
为了验证哥德巴赫猜想对100以内的正偶数是成立的，要将正偶数分解为两部分，在对这两部分进行判断，如果均是素数则满足题意，不是则重新分解继续判断。本实例把素数的判断过程自定义到函数ss中，对每次分解出的两个数只要调用函数ss来判断即可。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include<stdio.h>
（3）自定义ss函数，函数类型为基本整型，作用是判断一个数是否为素数。代码如下：
int ss（int i） /*自定义函数判断是否为素数*/
{
int j;
if（i<=1） /*小于1的数不是素数*/
return 0;
if（i==2） /*2是素数*/
return 1;
for（j=2;j<i;j++） /*对大于2的数进行判断*/
{
if（i % j = = 0）
return 0;
else if（i != j + 1）
continue;
else
return 1;
}
}
（4）对6～100的正偶数进行拆分，再对拆分出来的数分别调用函数ss进行是否为素数的判断。若均为素数，则按指定格式输出，否则继续下次循环，重新进行拆分及判断。
（5）主要程序代码如下：
main（）
{
int i, j, k, flag1, flag2, n = 0;
for（i = 6; i < 100; i += 2）
for（k = 2; k <= i / 2; k++）
{
j = i - k;
flag1=ss（k）; /*判断拆分出的数是否是素数*/
if（flag1）
{
flag2 = ss（j）;
if（flag2） /*如果拆分出的两个数均是素数则输出*/
{
printf（"%3d=%3d+%3d,", i, k, j）;
n++;
if（n % 5 = = 0）
printf（"\n"）;
}
}
}
}
举一反三
根据本实例，读者可以：
取一个整数a从右端开始的4～7位。
有n个整数，使其前面各数顺序向后移m个位置，最后m个数变成最前面的m个数。
实例132 四方定理
这是一个可以提高分析能力的实例
实例位置：光盘\mingrisoft\04\132
实例说明
四方定理的内容是：所有的自然数至多只要用4个数的平方和就可以表示。编程验证该定理。运行结果如图4.22所示。
图4.22 四方定理
技术要点
本实例对4个变量i、j、k、l采用穷举试探的方法进行计算，当满足定理中的条件时输出计算结果。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）程序中采用4个for循环语句分别对i、j、k、l的值进行试探，对满足if条件语句中条件的将其按指定格式输出，输出完退出程序。
（4）主要程序代码如下：
main（）
{
long i,j,k,l,n; /*定义变量为长整型*/
printf（"please input a number:\n"）;
scanf（"%ld",&n）; /*定义变量为长整型*/
for（i=0;i<=n;i++） /*对i，j，k，l进行穷举*/
for（j = 0; j <= i; j++）
for（k = 0; k <= j; k++）
for（l = 0; l <= k; l++）
if（i*i+j*j+k*k+l*l==n） /*判断是否满足定理要求 */
{
printf（"%ld*%ld+%ld*%ld+%ld*%ld+%ld*%ld=%ld\n",i,i,j,j,k,k,l,l,n）; /*将满足要求的结果输出*/
exit（0）;
}
}
举一反三
根据本实例，读者可以：
编程实现输入n为偶数时，调用函数求1/2+1/4+...+1/n，当输入n为奇数时，调用函数1/1+1/3+...+1/n。
1000！末尾有多少个0，编程计算。
实例133 尼科彻斯定理
这是一个可以提高分析能力的实例
实例位置：光盘\mingrisoft\04\133
实例说明
尼科彻斯定理内容是：任何一个整数的立方都可以写成一串连续奇数的和。编程验证该定理。运行结果如图4.23所示。
图4.23 尼科彻斯定理
技术要点
解决本实例的关键是先要确定这串连续奇数中的最大值的范围，这里我们可以这样分析，任何立方值（这里设为sum）的一半（这里设为x）如果是奇数，则x+x+2的值一定大于sum，那么这串连续奇数的最大值不会超过x；如果x是偶数，我们需把它变成奇数，那么变成奇数到底是加1、减1还是其他呢？这里我们选择加1，因为x+1+x-1正好等于sum，所以当x是偶数时这串连续奇数的最大值不会超过x+1。在确定了范围后，我们就可以从最大值开始进行穷举。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）程序中使用了两个while循环语句，第一个while语句的功能是从可能的最大值开始直到1为止进行穷举，第二个while循环的功能是通过第一个while循环所确定的i值进行每次减2逐次累加求和，当累加和等于立方值时输出累加过程并跳出循环，当累加和大于立方值时也同样条出第二个循环回到第一个循环中。
（4）主要程序代码如下：
main（）
{
int i, j, k = 0, l, n, m, sum,flag=1;
printf（"\n please input a number:\n"）;
scanf（"%d",&n）; /*从键盘中任意输入一个数*/
m=n*n*n; /*计算出该数的立方*/
i = m / 2;
if（i % 2==0） /*当i为偶数时i值加1*/
i = i + 1;
while（flag==1&&i>=1） /*当i大于等于1且flag=1时执行循环体语句*/
{
sum = 0;
k = 0;
while（1）
{
sum+=（i-2*k）; /*奇数累加求和*/
k++;
if（sum==m） /*如果sum与m相等，则输出累加过程*/
{
printf（"%d*%d*%d=%d=", n, n, n, m）;
for（l = 0; l < k -1; l++）
printf（"%d+", i - l * 2）;
printf（"%d\n",i-（k-1）*2）; /*输出累加求和的最后一个数*/
flag=0;
break;
}
if（sum > m）
break;
}
i-=2; /*i等于下一个奇数继续上面过程*/
}
}
举一反三
根据本实例，读者可以：
输入任意数n，求n！末尾有多少个0。
一个四位数前两位数相同、后两位数相同、相互间又不同，且是另一个整数的平方，求该四位数。
4.5 逻辑推理与判断
很多的逻辑推理题需要大量的演算，而且常常会因来回推导使自己陷入混乱，如果用程序的方法来解决逻辑推理题就会避免出现来回推导的过程，这样就不用花费大量时间。本节介绍了几个用程序解决逻辑推理问题的实例，对读者今后再做这方面的题相信会有很大帮助。
实例134 婚礼上的谎言
这是一个可以启发思维的实例
实例位置：光盘\mingrisoft\04\134
实例说明
三对情侣参加婚礼，3个新郎为A、B、C、3个新娘为X、Y、Z，有人想知道究竟谁和谁结婚，于是就问新人中的3位，得到如下的提示：A说他将和X结婚，X说她的未婚夫是C，C说他将和Z结婚。事后知道他们在开玩笑，说的全是假话，那么究竟谁与谁结婚呢？运行结果如图4.24所示。
图4.24 婚礼上的谎言
技术要点
解决本实例的算法思想如下。
用“a=1”表示新郎a和新娘x结婚，同理如果新郎a不与新娘x结婚则写成“a！=1”根据题意得到如下的表达式：
a！=1 a不与x结婚
c！=1 c不与x结婚
c！=3 c不与z结婚
我们在分析题的时候还要发现题中隐含的条件，即3个新郎不能互为配偶，则有：a!=b且b!=c且a!=c。穷举所有可能的情况，代入上述表达式进行推理运算。如果假设的情况使上述表达式的结果为真，则假设的情况就是正确的结果。
实现过程
（1）在TC中创建一个C文件。
（2）引用头文件：
#include <stdio.h>
（3）利用for循环对a、b、c所有情况进行穷举，使用if语句进行条件判断。
（4）主要程序代码如下：
main（）
{
int a, b, c;
for（a=1;a<=3;a++） /*穷举a的所有可能*/
for（b=1;b<=3;b++） /*穷举b的所有可能*/
for（c=1;c<=3;c++） /*穷举c的所有可能*/
if（a != 1 && c != 1 && c != 3 && a != b && a != c && b != c）
/*如果表达式为真，则输出结果，否则继续下次循环*/
{
printf（"%c will marry to a\n", 'x' + a -1）;
printf（"%c will marry to b\n", 'x' + b -1）;
printf（"%c will marry to c\n", 'x' + c -1）;
}
}
举一反三
根据本实例，读者可以：
某抢险队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有以下限制条件：A和B两人中至少去一人；A和D不能一起去；A、E和F三人中要派两人去；B和C都去或都不去；C和D两人中去一个；若D不去，则E也不会去问应当派那几个人去？
在审问四名盗窃嫌疑人时：A说：“B没偷，D偷的”；B说：“我没偷，C偷得”；C说：“A没偷，B偷的”；D说“我没偷”。则四名犯罪嫌疑人中的每个人要么是诚实的，要么总是说谎。根据回答判断这四个人中谁是窃贼。