头歌-贪心算法
第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元）
预期输出：
#include <stdio.h>
int greedy_coin_change(int amount) {
// 定义面值数组和对应的纸币名称
int coins[] = {100, 50, 20, 10, 5, 2, 1};
const char *coin_names[] = {"100元", "50元", "20元", "10元", "5元", "2元", "1元"};
// 初始化计数器
int count = 0;
// 计算找零
for (int i = 0; i < sizeof(coins) / sizeof(coins[0]); i++) {
// 计算当前面值的纸币张数
int num_coins = amount / coins[i];
// 输出当前面值纸币的张数和名称
printf("%s %d张\n", coin_names[i], num_coins);
// 更新剩余的金额
amount %= coins[i];
}
return count;
}
int main() {
// 获取需要找给顾客的钱
int n;
scanf("%d", &n);
// 调用贪婪算法计算最少需要的钱币张数
int result = greedy_coin_change(n);
// 输出结果
return 0;
}
第2关：求一个数列的极差
本关任务：将 n 个正整数作成的一个数列，进行如下操作：每一次删除其中的两个数 a 和 b，然后在数列中加入一个数a×b+1，如此下去直至数列中剩下一个数。
在所有按这种操作方式最后得到的数中，最大的记作 max，最小的记作 min，则该数列的极差定义为M=max-min，请你使用贪心算法设计编程输出他们的极差。
编程要求
请在右侧编辑器Begin-End处补充代码，完成本关任务（注意已经为你获取输入数据）。
测试说明
平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：
测试输入：
7 //输入7（n）个整数3 //此行及以下为具体的每个数据579111315
预期输出：Max=max-min=2221298-2038489=182809
#include <stdio.h>
/********* Begin **********/
int s1,s2;
void max2(int a[],int n)
{
int j;
if(a[1]>=a[2])
{
s1=1;
s2=2;
}
else
{
s1=2;
s2=1;
}
for (j=3;j<=n;j++)
{
if(a[j]>a[s1])
{
s2=s1;
s1=j;
}
else if(a[j]>a[s2])
s2=j;
}
}
int calculatemin(int a[],int n)
{
while (n>2)
{
max2(a,n);
a[s1]= a[s1]* a[s2]+1;
a[s2]=a[n];
n=n-1;
}
return(a[1]* a[2]+1);
}
void min2(int a[ ],int n)
{
int j;
if(a[1]<=a[2])
{
s1=1;
s2=2;
}
else
{
s1=2;
s2=1;
}
for (j=3;j<=n;j++)
{
if (a[j]<a[s1])
{
s2=s1;
s1=j;
}
else if (a[j]<a[s2])
s2=j;
}
}
int calculatemax(int a[],int n)
{
while (n>2)
{
min2(a,n);
a[s1]= a[s1]* a[s2]+1;
a[s2]=a[n];
n=n-1;
}
return(a[1]* a[2]+1);
}
int length(int a[])
{
int i=1;
while(a[i]!=0)
{
i++;
}
return i-1;
}
int main()
{
int i,n,b[100],max,min,num;
scanf("%d",&num);
int a[num+1];
for (i=1;i<=num;i++)
scanf("%d",&a[i]);
for (i=1;i<=num;i++)
b[i]=a[i];
min= calculatemin(a,num);
max= calculatemax(b,num);
printf("Max=max-min=%d-%d=%d\n",max,min,max-min);
}
/********* End **********/
第3关：将真分数用埃及分数之和表示
任务描述
本关任务：设计一个算法，把一个真分数 F 表示为埃及分数之和的形式。
编程要求
请在右侧编辑器Begin-End处补充代码，完成本关任务，注意需要学生自己获取真分数再进行编程。
测试说明
平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：
测试输入：3 5（3为分子，5为分母，真分数为3/5）
预期输出：3/5=1/2+1/10
#include "stdio.h"
void main()
{
/********** Begin **********/
int a,b,c;
scanf("%d %d",&a,&b);
if(a>=b)
printf("输入错误");
else
if(a==1 || b%a==0)
{
printf("%d/%d=1/%d",a,b,b/a);
}
else
{
printf("%d/%d=",a,b);
while(a!=1)
{
c = b/a+1;
a = a*c - b;
b = b*c;
printf("1/%d",c);
if(a>=1)
printf("+");
if(b%a ==0 || a==1)
{
printf("1/%d",b/a);
a=1;
}
}
}
printf("\n");
/********** End **********/
}
第4关：找到出现次数最多的数
任务描述
本关任务：给定 n 个正整数，编写一个实验程序找出它们中出现次数最多的数。如果这样的数有多个，输出其中最小的一个。
编程要求
请在右侧编辑器Begin-End处补充代码，完成本关任务。
测试说明
平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：
测试输入：
6 //给定6（n）个正整数10 //此行及以下为具体的每个数据110203020
预期输出：出现次数最多的且最小的数为10
#include <stdio.h>
using namespace std;
#include<algorithm>
/********** Begin **********/
int find(int n,int * a)
{
int maxn=0,bestd,num=1,i=1;
sort(a,a+n);
int pred=a[0];
while(i<n)
{
while(i<n&&a[i]==pred)
{
num++;
i++;
}
if(num>maxn)
{
bestd=pred;
maxn=num;
}
pred=a[i];
num=1;
i++;
}
return bestd;
}
int main()
{
int n,bestd,i;
scanf("%d",&n);
int a[n];
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bestd=find(n,a);
printf("出现次数最多的且最小的数为%d\n",bestd);
return 0;
}
/********** End **********/
第5关：将给定的整数去掉任意个数字后重新组成最小整数
任务描述
本关任务：键盘输入一个高精度的正整数 n，去掉其中任意 s 个数字后剩下的数字按原左右次序将组成一个新的正整数。
编程对给定的 n 和 s，寻找一种方案使得剩下的数字组成的新数最小。
编程要求
请在右侧编辑器Begin-End处补充代码，完成本关任务。
测试说明
平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：
测试输入：
231183 //正整数n3 //去掉3（s）个数字
预期输出：113
#include <bits/stdc++.h>
using namespace std;
int main() {
/********* Begin ********/
int k;
string s;
cin >> s >> k;
if (k > s.size()) {
cout << "Invalid Input.";
}
while (k) {
int i;
for (i = 0; i < s.size() - 1 && s[i] <= s[i + 1]; i++);
s.erase(i, 1);
k--;
}
if (s.empty()) {
cout << 0 << endl;
}
int i = 0;
for (i = 0; i < s.size()-1;) {
if (s[i] == '0') i++;
else break;
}
cout << s.substr(i);
return 0;
/********* End ********/
}
原文地址：https://blog.csdn.net/SXXYNHHXX/article/details/136718930
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！