算法设计与分析实训-找零钱&找到出现次数最多的数
本文最后更新于 230 天前,其中的信息可能已经有所发展或是发生改变。

第1关:找零钱

任务描述

本关任务:设计一个贪婪算法,使得找的钱币张数最少。

商店售货员找给 1 个顾客 n 元,用以下七种面值的纸币:100 元,50 元,20 元,10 元,5 元,2 元,1 元。

思考:如果商店售货员找给 1 个顾客 140 元,假设钱币的面值有九种:100 元,70 元,50 元,20 元,10 元,7 元,5 元,2 元,1 元。用贪婪算法得到的是该问题的最优解吗?

编程要求

请在右侧编辑器Begin-End处补充代码,完成本关任务,注意需要学生自己获取找的钱 n。

测试说明

平台会对你编写的代码进行测试,比对你输出的数值与实际正确数值,只有所有数据全部计算正确才能通过测试:

测试输入:123(需要找给顾客的钱 n元)

预期输出: 100元 1张 50元 0张 20元 1张 10元 0张 5元 0张 2元 1张 1元 1张

#include <stdio.h>

void main()
{
    /**********  Begin  **********/
    int size[7]={100,50,20,10,5,2,1};
    int count[7]={0,0,0,0,0,0,0};
    int n;
    scanf("%d",&n);
    while(n){
        for(int i=0;i<7;i++){
            if(n>=size[i]){
                n -= size[i];
                count[i]++;
                break;
            }
        }
    }
    for(int i=0;i<7;i++){
        printf("%d元 %d张\n",size[i],count[i]);
    }


    /**********  End  **********/
}

第2关:找到出现次数最多的数

任务描述

本关任务:给定 n 个正整数,编写一个实验程序找出它们中出现次数最多的数。如果这样的数有多个,输出其中最小的一个。

编程要求

请在右侧编辑器Begin-End处补充代码,完成本关任务。

测试说明

平台会对你编写的代码进行测试,比对你输出的数值与实际正确数值,只有所有数据全部计算正确才能通过测试:

测试输入:

  1. 6 //给定6(n)个正整数
  2. 10 //此行及以下为具体的每个数据
  3. 1
  4. 10
  5. 20
  6. 30
  7. 20

预期输出:出现次数最多的且最小的数为:10

#include <stdio.h>
#include <iostream>
using namespace std;
#include<algorithm>

/**********  Begin  **********/

int main()
{
    int n;      cin >> n;
    int a[n];   for (int i = 0; i < n; i++){cin >> a[i];}
    int maxMode=0,maxModeCount=0,nowCount=1;
    sort(a, a+n);
    for(int i=n-2 ; i>=0; i--){
        if(nowCount >= maxModeCount){
            maxMode = a[i+1];
            maxModeCount = nowCount;
        }
        if(a[i] == a[i+1]){
            nowCount++;
        }else{
            nowCount = 1;
        }
    }

    cout<<"出现次数最多的且最小的数为:"<<maxMode;
    return 0;
}
/**********  End  **********/

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇