gaowencheng01
cskyLine
采纳率100%
2020-01-13 00:32 阅读 294
已采纳

新手c语言编程穷举问题

有四种面值不一样的货币分别是10元，5元，2元，1元。现在给你一个钱数你能求求它的组成方法都有多少吗？

运行时间尽可能短

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • 已采纳
    caozhy 从今以后生命中的每一秒都属于我爱的人 2020-01-13 11:10

    问题解决的话，请点下采纳，谢谢

    // Q1051673.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <stdio.h>
#include <string.h>

void solve(int * seed, int nseed, int * cand, int ncand, int target)
{
    if (target == 0)
    {
        for (int i = 0; i < nseed; i++)
        {
            printf("%d ", seed[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < ncand; i++)
    {
        if (target >= cand[i] && cand[i] <= seed[nseed - 1])
        {
            int * seed1 = new int[nseed + 1];
            memcpy(seed1, seed, nseed * sizeof(int));
            seed1[nseed] = cand[i];
            solve(seed1, nseed + 1, cand, ncand, target - cand[i]);
            delete[] seed1;
        }
    }
}

int main()
{
    int cand[4] = { 10, 5, 2, 1 };
    int target = 25; //钱数
    for (int i = 0; i < 4; i++)
    {
        int * seed = new int[1];
        seed[0] = cand[i];
        solve(seed, 1, cand, 4, target - seed[0]);
        delete[] seed;
    }
}

    10 10 5
    10 10 2 2 1
    10 10 2 1 1 1
    10 10 1 1 1 1 1
    10 5 5 5
    10 5 5 2 2 1
    10 5 5 2 1 1 1
    10 5 5 1 1 1 1 1
    10 5 2 2 2 2 2
    10 5 2 2 2 2 1 1
    10 5 2 2 2 1 1 1 1
    10 5 2 2 1 1 1 1 1 1
    10 5 2 1 1 1 1 1 1 1 1
    10 5 1 1 1 1 1 1 1 1 1 1
    10 2 2 2 2 2 2 2 1
    10 2 2 2 2 2 2 1 1 1
    10 2 2 2 2 2 1 1 1 1 1
    10 2 2 2 2 1 1 1 1 1 1 1
    10 2 2 2 1 1 1 1 1 1 1 1 1
    10 2 2 1 1 1 1 1 1 1 1 1 1 1
    10 2 1 1 1 1 1 1 1 1 1 1 1 1 1
    10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    5 5 5 5 5
    5 5 5 5 2 2 1
    5 5 5 5 2 1 1 1
    5 5 5 5 1 1 1 1 1
    5 5 5 2 2 2 2 2
    5 5 5 2 2 2 2 1 1
    5 5 5 2 2 2 1 1 1 1
    5 5 5 2 2 1 1 1 1 1 1
    5 5 5 2 1 1 1 1 1 1 1 1
    5 5 5 1 1 1 1 1 1 1 1 1 1
    5 5 2 2 2 2 2 2 2 1
    5 5 2 2 2 2 2 2 1 1 1
    5 5 2 2 2 2 2 1 1 1 1 1
    5 5 2 2 2 2 1 1 1 1 1 1 1
    5 5 2 2 2 1 1 1 1 1 1 1 1 1
    5 5 2 2 1 1 1 1 1 1 1 1 1 1 1
    5 5 2 1 1 1 1 1 1 1 1 1 1 1 1 1
    5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    5 2 2 2 2 2 2 2 2 2 2
    5 2 2 2 2 2 2 2 2 2 1 1
    5 2 2 2 2 2 2 2 2 1 1 1 1
    5 2 2 2 2 2 2 2 1 1 1 1 1 1
    5 2 2 2 2 2 2 1 1 1 1 1 1 1 1
    5 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
    5 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
    5 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    5 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    5 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    2 2 2 2 2 2 2 2 2 2 2 2 1
    2 2 2 2 2 2 2 2 2 2 2 1 1 1
    2 2 2 2 2 2 2 2 2 2 1 1 1 1 1
    2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1
    2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1
    2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1
    2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1
    2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    Press any key to continue . . .

    点赞 2 评论 复制链接分享
提交

相关推荐