给你一百元，帮我买100只鸡回来

发表于 | | 阅读次数:
字数统计: 1,369 字 | 阅读时长 ≈ 7 分钟

前言

本篇是大学《算法》课程的实验报告，这份报告包含了从原理分析到实验结果展示，有理有据地证明了好的方案会是多么地高效。

问题描述

我国古代数学家张丘建在《算经》一书中曾提出过著名的「百钱买百鸡」问题，该问题叙述如下：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？

翻译过来，公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱，现在要用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各多少只？

解决方案

这里，我们先假设：

  • a：鸡翁数
  • b：鸡母数
  • c：鸡雏数

方案一：穷举法

三个值的范围如下，让计算机进行循环判断即可。

$a \in [0,100]$

$b \in [0,100]$

$c \in [0,100]$

1
2
3
n=100
if((a+b+c == n)&&(5*a + 3*b + c/3 == n)&&(c%3==0))
{ OK!}

三层遍历循环，该方案的时间复杂度即为$O(n^3)$

方案二：变量代替法

在算法1的基础上，将搜索的范围和层数缩小。

$c = 100 - a -b$

$a \in [0,100/5]$

$b \in [0,100/3]$

1
2
3
4
n = 100
c = n -a-b;
if(5*a + 3*b + c/3 == n && c%3==0)
{OK!}

两层遍历循环，该方案的时间复杂度即为$O(n^2)$

方案三：推导法

这里，我们进行推导，很容易就知道要满足下面这两个条件：
$$
\begin{cases}
5 a + 3 b + \frac 13 c = 100 \
a + b + c = 100
\end{cases}
$$
消除$c$后
$$
7a + 4b = 100
$$
为了消除$b$前面的系数4，不妨令$a = 4k$ ,即$b=25-7k$ ,由$a$和$b$的范围可得：

$$
\begin{cases}
0 \leq 4k \leq 20\
0\leq 25-7k \leq \frac {100}3
\end{cases}
$$
解出$k$的范围为$k\in[0,\frac {25}7]$
只要遍历$k$的值，即可求解，该方案的时间复杂度即为$O(n)$

实验对照

下面我们将计算机得到的结果进行罗列，让我们能更好地对三种算法进行比较。

实验可能的解

公鸡0只，母鸡25只，小鸡75只;

公鸡4只，母鸡18只，小鸡78只;

公鸡8只，母鸡11只，小鸡81只;

公鸡12只，母鸡4只，小鸡84只;

实验对比：

这里我们为了测试三种算法到底差别多少，不妨将规模提升到n元买n鸡问题。

软件：codeblocks

表格1：三种算法对比

规模 算法1 算法2 算法3
n=100 0.01s <0.0000001s <0.0000001s
n=6000 616.14s 0.31s 0.14s
n=50000 >1000s 1.31s 0.24s
n=200000 >1000s 10.90s 1.00s
n=500000 >1000s 64.82s 2.66s
n=800000 >1000s 148.63s 3.61s
n=2000000 >1000s 920.05s 9.86s
n=5000000 >1000s >1000s 30.61s
n=10000000 >1000s >1000s 59.81s

结果分析

当算法1到了n=6000以上的规模，就需要花费大量时间，超过1000s。

算法2与算法3在n=50000开始显示出差别，随着n的提升，两个算法之间耗时差距越来越大。

当n=2000000时，算法2需要消耗920s，而算法3只需要9.86s。

当n=10000000时，算法3耗时59.819s，相当于算法二在n=500000时所用的时间。

可见当我们的规模越大时，时间消耗的差距就会体现的越大。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

int g[1000000],m[1000000],s[1000000];
void chicken_question(int n,int &k,int g[],int m[],int s[]);
void chicken_question2(int n,int &k,int g[],int m[],int s[]);
void chicken_question3(int n,int &k,int g[],int m[],int s[]);

int main()
{
int k=0;
int n=15000000,c=0;
double  duration1,duration2,duration3;
clock_t start, finish;
printf("请输入n的值\n");

start = clock();
chicken_question(n,k,g,m,s);
finish = clock();
duration1 = (double)(finish - start)/ CLOCKS_PER_SEC;  //转化为秒
printf( "\n算法1运行%d次的时间为%f seconds\n",n,duration1 );
start = clock();
chicken_question2(n,k,g,m,s);
finish = clock();
duration2 = (double)(finish - start)/ CLOCKS_PER_SEC;  //转化为秒*/
start = clock();
chicken_question3(n,k,g,m,s);
finish = clock();
duration3 = (double)(finish - start)/ CLOCKS_PER_SEC;  //转化为秒
printf( "\n算法2运行%d次的时间为%f seconds\n",n,duration2 );
printf( "\n算法3运行%d次的时间为%f seconds\n",n,duration3 );
system("pause");//
return 0;
}

// 公鸡 母鸡 小鸡的数目为 g[] m[] s[]  三种鸡购买的总数目为n  问题的解数目为k
void chicken_question(int n,int &k,int g[],int m[],int s[])
{
int a,b,c;
k = 0;
for (a=0;a<=n;a++)
{
	for(b=0;b<=n;b++)
	{
		for(c=0;c<=n;c++)
		{
			  if((a+b+c == n)&&(5*a + 3*b + c/3 == n)&&(c%3==0))
			  {
			  g[k] = a;
			  m[k] = b;
			  s[k] = c;
            //printf("g[%d]=%d,m[%d]=%d,s[%d]=%d\n",k,a,k,b,k,c);
			  k++;

			  }
		}
	}
}
}

void chicken_question2(int n,int &k,int g[],int m[],int s[])
{
int i,j,a,b,c;
k = 0;
i = n/5;
 j = n/3;
for (a=0;a<=i;a++)
{

	for(b=0;b<=j;b++)
	{
	    c = n -a-b;
 if(5*a + 3*b + c/3 == n && c%3==0)
			  {
			  g[k] = a;
			  m[k] = b;
			  s[k] = c;
              printf("g[%d]=%d,m[%d]=%d,s[%d]=%d\n",k,a,k,b,k,c);
			  k++;
			  }

	}
}
}


void chicken_question3(int n,int &k,int g[],int m[],int s[])
{
int x,y,z;
k = 0;
for(int k1=0;k1<=n/28;k1++)
{

    x = 4*k1;
    y = n/4 -7*k1;
    z = (3*n)/4+3*k1;
       if(5*x + 3*y + z/3 == n && z%3==0)
        {
            g[k] = x;
            m[k] = y;
            s[k] = z;
            printf("g[%d]=%d,m[%d]=%d,s[%d]=%d\n",k,x,k,y,k,z);
            k++;
        }

}