每日一算法:百元百鸡

栏目: 编程工具 · 发布时间: 6年前

内容简介: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)

每日一算法:百元百鸡


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Is Parallel Programming Hard, And, If So, What Can You Do About

Is Parallel Programming Hard, And, If So, What Can You Do About

Paul E. McKenney

The purpose of this book is to help you understand how to program shared-memory parallel machines without risking your sanity.1 By describing the algorithms and designs that have worked well in the pa......一起来看看 《Is Parallel Programming Hard, And, If So, What Can You Do About 》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器