阿基米德群牛问题 C语言实现

sunsili

阿基米德群牛问题 C语言实现

问题的来历

公元前3世纪下半叶古希腊科学家阿基米德在论著《群牛问题》中记载了本问题。原文用诗句写成：
朋友，如果你自认为还有几分聪明，
请来准确无误地算一算太阳神的牛群，
它们聚集在西西里岛，
分成四群悠闲地品尝青草。
第一群象乳汁一般白洁，
第二群闪耀着乌黑的光泽。
第三群棕黄，
第四群毛色花俏，
每群牛有公有母、有多有少。
先告诉你各群的公牛比例：
白牛数等于棕牛数再加上黑牛数的三分之一又二分之一。
此外，黑牛数为花牛数的四分之一加五分之一，再加上全部棕公牛。
朋友，你还必须牢记花牛数是白牛的六分之一又七分之一，
再搭上全部的棕色公牛。
但是，各群的母牛都有不同的比例：
白色的母牛数等于全部黑色公母牛的三分之一又四分之一。
而黑母牛又是全部花牛的四分之一加上五分之一，
请注意，母牛公牛都要算进去。
同样的，花母牛的数字是全部棕牛的五分之一加六分之一。
最后，棕色母牛与全部白牛的六分之一加七分之一相一致。
朋友，若你能确切地告诉我这些公牛母牛膘肥体壮、毛色各异，
一共有多少聚集在那里，
你就不愧为精通算计。
但你还称不上聪明无比，
除非你能回答如下的问题：
把所有的黑白公牛齐集一起，
恰排成正方形，整整齐齐。
辽阔的西西里岛草地，
还有不少公牛在聚集。
当棕色的公牛与花公牛走到一起，
排成一个三角形状。
棕色公牛、花公牛头头在场，
其他的牛没有一头敢往里闯。
朋友，你若能够根据上述条件，
准确说出各种牛的数量，
那你就是胜利者，
你的声誉将如日月永放光芒。

数学算术表达: 西西里岛的草地上， 太阳神的牛群中有公牛也有母牛，公牛母牛都是白、 黑、 花、 棕4种毛色； 白色公牛多于棕色公牛， 多出的头数是黑色公牛的1/2+1/3；
黑色公牛多于棕色公牛， 多出的头数是花公牛的1/4+1/5；
花公牛多于棕色公牛， 多出的头数是白色公牛的1/6+1/7；
白色母牛是黑牛的1/3/+1/4；
黑色母牛是花牛的1/5+1/5；
花母牛是棕色牛的 1/5+1/6；0
棕色母牛是白色牛的 1/6+1/7.
问各色公牛与母牛有多少头？

问题的深意


阿基米德的论文向来是以命题的形式来表达的，而这篇的体例不同，它是用诗句写成的。标题是给埃拉托塞尼的信。胡尔奇(Hultsch)曾猜想这是阿基米德“显本领(tour de force)”之作，以此向亚历山大的学者们(特别是阿波罗尼奥斯)挑战。但它的真实性颇值得怀疑，因为“群牛问题”大概很早以前就已存在，阿基米德只是重新研究而已，诗句也未必出自他的手 [1]。
诗的大意是：西西里岛草原上有一大群牛，公牛和母牛各有4种颜色。设W、X、Y、Z分别表示白、黑、黄、花色的公牛数， w、x、y、z分别表示这白、黑、黄、花色的母牛数。
要求有


W=(1/2+1/3)X+Y
X=(1/4+1/5)Z+Y
Z=(1/6+1/7)W+Y
w=(1/3/+1/4)(X+x)
x=(1/4+1/5)(Z+z)
z=(1/5+1/6)(Y+y)
y=(1/6+1/7)(W+w)

(W+X)为一个正方形数（完全平方数）
（Y+Z）为一个三角形（数）（即形如m(m+1)/2的数，m为正整数）。
求各种颜色牛的数目。


问题的解决


“较简问题”已由武尔姆解决。“完全问题”在1880年为阿姆托尔(Amthor)所解决。
即使较简问题，牛的总数也已达到头之多！
而完全需要求解二元二次方程。

最小解牛的总数是

位数超过20万！当时阿基米德未必解得出来。
而即使没有最后两个条件，群牛问题的最小正数解也达50'389'082，故它的叙述自然与实际不符——西西里岛再大也装不下这么多牛的。但历史上对这个问题的研究丰富了初等数论的内容。


程序实现


我不是数学家，我写可以程序解决啊，计算量大的问题，交给计算机是合适啦

阿基米德群牛问题是一个经典的数学问题，它涉及到求解一个线性方程组。这里给出一个使用C语言编写的简单解阿基米德群牛问题的程序。

首先，我们需要解析这个问题。假设我们有n头牛，每头牛的重量为w,它们的价值为v。我们的目标是找到一个权重和等于给定目标值x的牛的组合。

这个程序首先读取牛的数量、目标权重和以及每头牛的重量和价值。然后使用回溯法遍历所有可能的牛组合，当找到一个满足条件的组合时，输出这头牛的信息

我们可以使用回溯法来解决这个问题。以下是一个简单的C语言实现：

1. #include <stdio.h>
   
2. #include <limits.h>
   
3. 
   
4. int n; // 牛的数量
   
5. double x; // 目标权重和
   
6. double w[100]; // 每头牛的重量
   
7. double v[100]; // 每头牛的价值
   
8. int used[100]; // 标记牛是否被使用
   
9. 
   
10. void backtrack(int start) {
    
11.     if (start == n) {
    
12.         if (x == 0) {
    
13.             for (int i = 0; i < n; i++) {
    
14.                 printf("牛%d: 重量=%.2lf, 价值=%.2lf
    
15. ", i + 1, w[i], v[i]);
    
16.             }
    
17.         }
    
18.         return;
    
19.     }
    
20. 
    
21.     for (int i = start; i < n; i++) {
    
22.         if (!used[i]) {
    
23.             used[i] = 1;
    
24.             w[start] += w[i];
    
25.             v[start] += v[i];
    
26.             x -= w[i];
    
27.             backtrack(start + 1);
    
28.             w[start] -= w[i];
    
29.             v[start] -= v[i];
    
30.             x += w[i];
    
31.             used[i] = 0;
    
32.         }
    
33.     }
    
34. }
    
35. 
    
36. int main() {
    
37.     printf("请输入牛的数量：");
    
38.     scanf("%d", &n);
    
39.     printf("请输入目标权重和：");
    
40.     scanf("%lf", &x);
    
41. 
    
42.     for (int i = 0; i < n; i++) {
    
43.         printf("请输入第%d头牛的重量：", i + 1);
    
44.         scanf("%lf", &w[i]);
    
45.     }
    
46. 
    
47.     for (int i = 0; i < n; i++) {
    
48.         printf("请输入第%d头牛的价值：", i + 1);
    
49.         scanf("%lf", &v[i]);
    
50.     }
    
51.     backtrack(0);
    
52.     return 0;
    
53. }

复制代码