个人笔记：算法讲座1.3——海盗分金（贪心算法）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了个人笔记：算法讲座1.3——海盗分金（贪心算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2080字，纯文字阅读大概需要3分钟。
内容图文
本文仅供学习参考使用，谢谢
目录：
问题描述：
Alice和Bob穿越成了加勒比的海盗。有一次海盗们发现了一个大的宝藏，金币总额M的位数比海盗们的人数还多!他们靠决斗产生了海盗的排位，并约定，无论面对的金币数量是多少，都需要在这个数目的基础上划掉位作为给下一个海盗的数目。每个海盗都希望自己拿到的金币数量最多，井假设他们都是聪明的；都知道要怎么做才能保证自己拿到最多的金币。Bob经过激烈的搏斗拿到了第4的排名，他能拿到金币的数目为N：(特别强调，所有数目里都没有0 )，问，他可以拿到多少金币？
- 输入：
M
- 输出：
N
算法思想：
涉及到一个小知识点——如何将字符串型的数据转化为int型：
比如——char型 ‘4’ - ‘0’ = int型 4
凑合凑合，懒得写了。。。。
测试数据：
- 数据1:
394256
- 结果1:
231
- 数据2:
263574982
- 结果2:
211500
代码：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define maxsize 15
typedef struct {
int L[maxsize];//按位存放 金钱数目
int visited[maxsize];//0未读 1已读
int num;//钱是几位数
}Money;
int readread(Money X){
int M = 0,tmp = 0;
for (int i=0; i<X.num; i++) {
if (X.visited[i]==0) {
tmp=X.L[i];
M=M*10+tmp;
}
}
return M;
}
int getnext(Money X){//删掉一位数后的最小值 这个值给下一个人
int min=0,tmp=0;
// printf("%d\n",X.num);
// printf("%d\n",readread(X));
for (int i=0; i<X.num; i++) {
X.visited[i]=1;
tmp=readread(X);
if (min==0) {
min=tmp;
} else {
if (tmp<min) {
min=tmp;
}
}
X.visited[i]=0;
}
return min;
}
Money linklink(Money X){//德国骨科接骨
int min=getnext(X);
int real=min,c=0;
Money tmp=X;
for (int i=X.num-2; i>=0; i--) {
c=real%10;
tmp.L[i]=c;
real/=10;
}
tmp.num=X.num-1;
return tmp;
}
int main(int argc, const char * argv[]) {
Money name[5];// A0 B1 C2 D3 E4
char *express=(char*)malloc(sizeof(char)*maxsize);
gets(express);
char *get=express;
for (int i=0; *get; get++,i++){//给A0参数 num=实际位数
name[0].L[i]=*get-'0';
name[0].num=i+1;
}
for (int i=0; i<maxsize; i++)//将表内的所有visite标记为0
for (int j=0; j<maxsize; j++)
name[i].visited[j]=0;
for (int i=1; i<=4; i++) {
name[i]=linklink(name[i-1]);
}
int end=0;
// end=readread(name[0]);
// end=getnext(name[0]);
// end=readread(linklink(name[0]));
end=readread(name[3])-readread(name[4]);
printf("%d\n",end);
return 0;
}
内容总结
以上是互联网集市为您收集整理的个人笔记：算法讲座1.3——海盗分金（贪心算法）全部内容，希望文章能够帮你解决个人笔记：算法讲座1.3——海盗分金（贪心算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。