5.1.2 百元买百鸡问题
【问题】 已加公鸡5元一只，母鸡3元一只，小鸡1元三只，用100元钱买100只鸡， 问公鸡、母鸡、小鸡各多少只?
【想法】 设公鸡、母鸡和小鸡的个数分别为x、y、z，则有如下方程组成立，
则百元买百鸡问题转换为求方程组的解。应用蛮力法求力程组的解只能依次试探变量x、y和z的值，验证x、y和z的某个特定值是否能够使方程组成立。
【算法实现】设变量z、和z分别表示公鸡、母鸡和小鸡的个数，由于方程组可能有多个解，设变量 count 表示解的个数，注意到小鸡1元三只，在判断总价是否满足方程时要先判断：z是否是3的倍数。程序如下。
#include <iostream>
using namespace std;
void Chicken( )
{
int x, y, z, count = 0;
for (x = 0; x <= 20; x++)
{
for (y = 0; y <= 33; y++)
{
z = 100 - x - y; //满足共100只
if ((z % 3 == 0) && (5 * x + 3 * y + z/3 == 100)) //满足总价100元
{
count++; //解的个数加1
cout<<"公鸡："<<x<<" 母鸡："<<y<<" 小鸡："<<z<<endl;
}
}
}
if (count == 0)
cout<<"问题无解"<<endl;
}
int main( )
{
Chicken( );
return 0;
}
【算法分析】 算法由两层嵌套循环组成，基本语句是条件表达式((z%3== 0)&&(5* x+3*y+z/3== 100)),执行次数为21×34= 714。一般地，假设共买n只鸡，基本语句的执行次数为n/5*n/3=O(n*2).
5.2.1 顺序查找
【问题】顺序查找(sequential search)是在查找集合中依次查找值为k的元素。若查找成功，给出该元素在查找集合中的位置；若查找失败，则给出失败信息。
【想法1】 将查找集合存储在一维数组中，然后从数组的一端向另一端逐个将元素与待查值进行比较。若相等，则查找成功，给出该元素在查找集合中的序号；若整个数组检测完仍未找到与待查值相等的元素，则查找失败，给出失败的标志0.
【算法实现1】将查找集合存储在数组元素r[1]~r[n]中，下标i初始化在数组的高端，这样查找结束时，若查找成功，下标i的值即元素的序号，若查找失败，下标i的值即为失败标志0。注意，在查找过程中要检测比较位置是否越界，程序如下：
#include <iostream>
using namespace std;
int SeqSearch1(int r[ ], int n, int k)
{
int i = n;
while (i > 0 && r[i] != k) //检测比较位置是否越界
i--;
return i;
}
int main( )
{
int a[11] = { 0 };
cout << "输入十个数：" << endl;
for (int i = 1; i <= 10; i++) {
cin >> a[i];
}
for (int i = 1; i <= 10; i++) {
cout << a[i] << " ";
int result = SeqSearch1(a, 10, i); // 将 9 修改为 i，在每次循环中搜索当前元素在数组中的位置
cout << result << " "; // 输出搜索结果
}
return 0;
}
【算法分析1】 算法 SeqSearch1的时间主要耗费在条件表达式(i>0&&r[i]!=k), 设p表示查找第i个元素的概率，等概率情况下，执行次数为：
【想法2】 为了避免在查找过程中每一次比较后都要判断查找位置是否越界，可以设置观察哨(sentinel),即将待查值放在查找方向的“尽头”处，则比较位置至多移动到下标0处，也就是“哨兵”的位置。改进的查找过程如图5-1所示。
【算法实现2】设函数SeqSearch2实现改进的顺序查找算法，程序如下：
#include <iostream>
using namespace std;
int SeqSearch2(int r[ ], int n, int k)
{
int i = n;
r[0] = k; //设置哨兵
while (r[i] != k) //不用检测比较位置是否越界
i--;
return i;
}
int main( )
{
int i, n = 10, k, index, r[100] = {0, 10,15,24,6,12,35,40,98,55};
cout<<"请输入要查找的整数：";
cin>>k;
cout<<"查找元素的序号是："<<SeqSearch2(r, n, k)<<endl;
return 0;
}
【算法分析2】 算法 SeqSearch2的时间主要耗费在条件表达式(r[[i]!= k),设pi 表示查找第i个元素的概率，等概率情况下，执行次数为：
顺序查找算法和其改进算法的时间复杂度都是O(n),但是算法 SegSearchl1要执行两个判断，而算法 SegSearch2只执行一个判断。实验表明，改进算法在待查找集合的长度大于1000时，进行一次顺序查找的时间几乎减少一半