内容简介:100元买100只,题目:公鸡5元一只、母鸡3元一只、小鸡1元三只求100元买一百只,各可以买几只三个变量:公鸡数量为 x 母鸡数量为 y 小鸡数量为 z
100元买100只,题目:公鸡5元一只、母鸡3元一只、小鸡1元三只
求100元买一百只,各可以买几只
三个变量:公鸡数量为 x 母鸡数量为 y 小鸡数量为 z
满足条件:
①:x+y+z=100
②:5x+3y+z/3=100
以上为计算题目得出方程
/** * 公鸡5元一只、母鸡3元一只、小鸡1元三只 * 求100元买一百只,各可以买几只 * 三个变量:公鸡数量为 x 母鸡数量为 y 小鸡数量为 z * 满足条件:x+y+z=100 5x+3y+z/3=100 * 以上为计算题目得出方程 */ void bj(int amount, int num) { int x, y, z = 0; // 公鸡数量 for (x = 0; x <= num; x++) { // 母鸡数量 for (y = 0; y <= num; y++) { // 小鸡数量 z = num - x - y; // 满足条件的 if (z % 3 == 0 && x * 5 + y * 3 + z / 3 == amount) { printf("公鸡:%d,母鸡:%d,小鸡:%d\n", x, y, z); } } } } int main(){ bj(100,100); return 0; }
以上不是最优的办法,因为最外层循环了 num 次,第二层循环也循环了 num次,这里可以得到一部分优化
void bj(int amount, int num) { int x, y, z = 0; // 公鸡数量 for (x = 0; x <= num / 5; x++) { // 母鸡数量 for (y = 0; y <= num / 3; y++) { // 小鸡数量 z = num - x - y; // 满足条件的 if (z % 3 == 0 && x * 5 + y * 3 + z / 3 == amount) { printf("公鸡:%d,母鸡:%d,小鸡:%d\n", x, y, z); } } } } int main() { bj(100, 100); return 0; }
这样的优化我们不必需要两个循环都循环num次了,只要循环符合amount的最大数,这样可以避免过多不必要的循环。
这样就是最优的解法了吗?当然不是,我们这里可以看到时间复杂度是:O(N2),那我们有没有办法优化到O(N)呢?
我们来看看结果:
公鸡:0,母鸡:25,小鸡:75
公鸡:4,母鸡:18,小鸡:78
公鸡:8,母鸡:11,小鸡:81
公鸡:12,母鸡:4,小鸡:84
我们来找一下规律,在这四条结果中,公鸡的规律是4的倍数,母鸡是7的递减,小鸡是3的递增。
我们还记得在一开始的时候提到的方程组:
①:x+y+z=100
②:5x+3y+z/3=100
上面两个方程组,有三个未知变量,为不定方程组
令②×3-①得:7x+4y=100
由 x+y+z = 100和5x + 3y + z/3 = 100可得7x+4y=100
则y = 25 -(7/4)X
再令x = 4k,则有y = 25 - 7k,继而z = 75 + 3k
因为 0 =< z <= 100,所以k的可能取值是0,1,2,3
void bj(int amount, int num) { int x, y, z = 0; for (int k = 1; k <= 3; k++) { x = 4*k; y = 25-7*k; z = 75+3*k; printf("公鸡:%d,母鸡:%d,小鸡:%d\n", x, y, z); } } int main() { bj(100, 100); return 0; }
以上的时间复杂度就可以为O(N)
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 通俗易懂--决策树算法、随机森林算法讲解(算法+案例)
- 限流算法之漏桶算法、令牌桶算法
- 什么是Paxos算法?Paxos算法是区块链核心算法之一
- 一文读懂对称加密算法、非对称加密算法和Hash算法
- 算法(六):图解贪婪算法
- 算法篇03:排序算法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
世界是平的(3.0版)
[美] 托马斯·弗里德曼 / 何帆、肖莹莹、郝正非 / 湖南科学技术出版社 / 2008-9 / 58.00元
世界变得平坦,是不是迫使我们跑得更快才能拥有一席之地? 在《世界是平的》中,托马斯·弗里德曼描述了当代世界发生的重大变化。科技和通信领域如闪电般迅速的进步,使全世界的人们可以空前地彼此接近——在印度和中国创造爆炸式增长的财富;挑战我们中的一些人,比他们更快占领地盘。3.0版新增两章,更新了报告和注释方面的内容,这些内容均采自作者考察世界各地特别是整个美国中心地带的见闻,在美国本土,世界的平坦......一起来看看 《世界是平的(3.0版)》 这本书的介绍吧!