C语言及程序设计进阶例程-27 贪心法问题求解-阿里云开发者社区

开发者社区> 贺利坚> 正文

C语言及程序设计进阶例程-27 贪心法问题求解

简介: 贺老师教学链接 C语言及程序设计进阶 本课讲解 找零钱问题及其求解 #include <stdio.h> int main ( ) { int money[10]={100,50,10,0}; /*最大面额的硬值面值排在最前面,将被优先处理*/ int x; /*找零金额*/ int i=0, n=0, m; scanf
+关注继续查看

贺老师教学链接 C语言及程序设计进阶 本课讲解

找零钱问题及其求解

#include <stdio.h>
int main ( )
{
    int money[10]={100,50,10,0};  /*最大面额的硬值面值排在最前面,将被优先处理*/
    int x;   /*找零金额*/
    int i=0, n=0, m;
    scanf("%d", &x); /*输入找零金额*/
    while(x>0 && money[i]!=0)   /**/
    {
        m=x/money[i];   /*要找多少个面额为money[i]的硬币。i初值为0,体现从币值最大的硬币开始考虑*/
        n+=m;           /*n初值为0,记录零钱总枚数*/
        x-=m*money[i];  /*剩余的零钱金额*/
        i++;            /*将继续考虑下一种面额的硬币*/
    }
    if(x==0)
        printf("%d\n", n);
    else
        printf("\n");
    return 0;
}

最优装载问题及其求解

#include <stdio.h>
#define N 5  /*最多可能集装箱数*/
int main()
{
    int w[N]; /*存放集装箱重量,w[i]是第i个集装箱的重量*/
    int x[N]= {0}; /*用来存放集装箱的取舍,x[i]为1,表示i集装箱要装船,为0不装*/
    int t[N];   /*用来存放w[i]的下标*/
    int c;    /*货船总载重量*/
    int n;    /*集装箱个数*/
    int i, j, tmpw, tmpt;    /*用于控制循环及用于交换的临时变量*/
    printf("输入货船的最大载重量:");
    scanf("%d", &c);
    printf("输入集装箱个数:");
    scanf("%d", &n);
    printf("输入每个集装箱的质量:\n");
    for(i=0; i<n; i++)
        scanf("%d", &w[i]);
    /*在数组t[]中记录下原先集装箱的下标*/
    for(i=0; i<n; i++)
        t[i]=i;
    /*步骤1:按集装箱重量排序,同时在t数组中保存原有的顺序*/
    for(i=0; i<n-1; i++)
        for(j=0; j<n-i-1; j++)
            /*如果前大后小,要交换*/
            if(w[j]>w[j+1])
            {
                tmpw = w[j];  /*交换w[]中的元素*/
                w[j] = w[j+1];
                w[j+1] = tmpw;
                tmpt = t[j];  /*同时交换代表他们原先下标的数组*/
                t[j] = t[j+1];
                t[j+1] = tmpt;
            }
    /*步骤2:根据排好序的数组w[],在不超重的情况下,确定哪些集装箱*/
    for(i=0; i<n && w[i]<=c; i++)
    {
        x[t[i]] = 1;     /*w[i]要装载,其原下标是t[i],所以x[t[i]] = 1*/
        c = c - w[i];    /*调整c值*/
    }
    /*步骤3:输出结果*/
    for(i=0; i<n; i++)
    {
        if(x[i]==1)
            printf("BOX:%d ", i);
    }
    return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
C语言及程序设计进阶例程-25 排序问题及其求解
贺老师教学链接 C语言及程序设计进阶 本课讲解 快速排序实现 #include&lt;stdio.h&gt; void quicksort(int data[],int first,int last) { int i, j, t, base; if (first&gt;last) return; base=data[first];
1024 0
C语言及程序设计进阶例程-28 动态规划法问题求解
贺老师教学链接 C语言及程序设计进阶 本课讲解 最短路径问题 #include&lt;stdio.h&gt; #define n 7 #define x 9999 /*用一个尽可能大的开销,代表结点之间没有通路*/ int map[n][n]= /*对图7.33中交通网的描述,map[i][j]代表i结点到j结点的开销*/ { {x,4,5,8,x,x,x
835 0
C语言及程序设计进阶例程-14 开发一个电子词典
贺老师教学链接  C语言及程序设计进阶 本课讲解 开发一个电子词典(下载词库点击打开链接) #include &lt;stdio.h&gt; #include&lt;string.h&gt; #include&lt;stdlib.h&gt; //定义词条类 typedef struct { char english[20]; char chinese[30]; cha
1100 0
《C语言程序设计进阶教程》一1.1 编译
本文讲的是C语言程序设计进阶教程一1.1 编译,本节书摘来华章计算机《C语言程序设计进阶教程》一书中的第1章,第1.1节, Intermediate C Programming[美] 陆永祥(Yung-Hsiang Lu) 著 徐东 译 译更多章节内容可以访问云栖社区“华章计算机”公众号查看。
2140 0
SAS进阶《深入解析SAS》之开发多语言支持的SAS程序
SAS进阶《深入解析SAS》之开发多语言支持的SAS程序 1. 多语言支持的应用程序是指该程序在世界给第使用时,其能够处理的数据,以及处理数据的方式、信息展现的方式都符合当地的语言、文化习惯,这要求应用程序运行时,能够自动进行与地区、语言相关的处理,也就是通常所说的国际化。 2. SBCS、DBCS、MBCS 单字节字符集SBCS指在该字符集中的字符最多由2个字
1665 0
或许有一两点你不知的C语言特性
关键字篇 volatile关键字 鲜为人知的关键字之一volatile,表示变量是'易变的',之所以会有这个关键字,主要是消除编译优化带来的一些问题,看下面的代码 1 int a = 8; 2 int b = a; 3 int c = a; 编译器认为,上面的第2句代码与第三句代码之间,没有存在对a赋值的语句,所以编译出来的汇编代码在讲a的值赋给c的时候,不会再次到内存取这个变量的值,而是取cache中的值。
814 0
C语言及程序设计进阶例程-29 枚举类型及其应用
贺老师教学链接 C语言及程序设计进阶 本课讲解 He先生方案一:用整型表示品牌、颜色 #include &lt;stdio.h&gt; int main( ) { int brand,color; //brand=0,1,2分别表示Lavida、Tiggo和Skoda //color=0,1,2分别表示红黑白 for(color=0; c
819 0
+关注
贺利坚
烟台大学计算机学院教师,建设系列学习资源,改革教学方法,为IT菜鸟建跑道,让大一的孩子会编程,为迷茫的大学生出主意,一起追求快乐的大学。 著书《逆袭大学:传给IT学子的正能量》,帮助处于迷茫中的大学
1965
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载