代码
比这篇新的文章:
C#如何取硬件标志代码
比这篇旧的文章: 计算Euler方程中 g(u) 的特征向量
作者: RainHousemin, 点击311次, 评论(0), 收藏者(0)
打分:
所有评论，共0条：( 我也来说两句)
比这篇旧的文章: 计算Euler方程中 g(u) 的特征向量
合并水果问题--- 求最小体力消耗----贪心算法(简单的贪心问题)
语言: C, 标签: 求最小体力消耗----贪心算法(简单的贪心问题) 合并水果问题--- 2008/09/04发布 4个月前更新 更新记录作者: RainHousemin, 点击311次, 评论(0), 收藏者(0)
001 /*问题描述:
002 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
003 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
004 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
005 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
006 */
007 /*
008 ============================================================================
009 Name : uniteFruits.c
010 Author : RainHouse.min
011 Version :
012 Copyright : 2008-2010
013 Description : 贪心算法。求合并水果的最小体力消耗
014 ============================================================================
015 */
016 #include <stdio.h>
017 #include <stdlib.h>
018
019 #include "figureSmallestExpend.h"
020
021 int main(void) {
022 int numFruits, count;
023 numFruits = count = 0;
024 int *numFruit;
025 numFruit = NULL;
026 puts(
027 "Pleause input the number of the fruits-kind AND the number of each one: "); /* prints */
028 scanf("%d", &numFruits);
029 numFruit = (int *) calloc(numFruits, sizeof(int));
030 if (numFruit == NULL) {
031 printf("*************Memerry Error!!!*************");
032 return EXIT_FAILURE;
033 }
034 getchar();
035
036 for (count = 0; count < numFruits; count++) {
037 *(numFruit + count) = getchar() - 48;
038 getchar();
039 }
040 /*printf("\n");
041 for (count = 0; count < numFruits; count++) {
042 printf("%d,", *(numFruit + count));
043 }
044 printf("\n");
045 */
046
047 printf("The smallest expend is:%d .\n", figureSmallestExpend(numFruit,
048 numFruits));
049 system("pause");
050 return EXIT_SUCCESS;
051 }
052
053
054 /*
055 * figureSmallestExpend.h
056 *
057 * Created on: 2008-9-4
058 * Author: WuYimin
059 */
060
061 #ifndef FIGURESMALLESTEXPEND_H_
062 #define FIGURESMALLESTEXPEND_H_
063
064 /*
065 *figure out the Smallest expend to move all of the fruits
066 *@args:int *--the array which use to record the number of every one fruit
067 *@args:int --the total number of the kinds of the fruits
068 *@return:int --the object--the smallest expend.
069 */
070 int figureSmallestExpend(int *, int);
071
072 #endif /* FIGURESMALLESTEXPEND_H_ */
073
074
075
076
077
078 /*
079 * figureSmallestExpend.c
080 *
081 * Created on: 2008-9-4
082 * Author: WuYimin
083 */
084 /*
085 *figure out the Smallest expend to move all of the fruits
086 *@args:int *--the array which use to record the number of every one fruit
087 *@args:int --the total number of the kinds of the fruits
088 *@return:int --the object--the smallest expend.
089 */
090
091 #include "figureSmallestExpend.h"
092
093 int figureSmallestExpend(int *weights, int kinds) {
094 int smallestExpend = 0;
095 int count = 2;
096 int *temp;
097 int tempswap;
098
099 if (kinds == 1)
100 return smallestExpend;
101 if (kinds == 2) {
102 smallestExpend += *weights + *(weights + 1);
103 return smallestExpend;
104 } else {
105 for (count = 2, temp = weights; count < kinds; count++) {
106 if (*temp > *(weights + count))
107 temp = weights + count;
108 else
109 continue;
110 }
111 tempswap = *temp;
112 *temp = *weights;
113 *weights = tempswap;
114
115 for (count = 2, temp = weights + 1; count < kinds; count++) {
116 if (*temp > *(weights + count))
117 temp = weights + count;
118 else
119 continue;
120 }
121 tempswap = *temp;
122 *temp = *(weights + 1);
123 *(weights + 1) = tempswap;
124 }
125
126 smallestExpend = *(weights + 1) = *weights + *(weights + 1);
127 smallestExpend = smallestExpend + figureSmallestExpend(weights + 1, kinds
128 - 1);
129 return smallestExpend;
130 }
002 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
003 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
004 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
005 例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
006 */
007 /*
008 ============================================================================
009 Name : uniteFruits.c
010 Author : RainHouse.min
011 Version :
012 Copyright : 2008-2010
013 Description : 贪心算法。求合并水果的最小体力消耗
014 ============================================================================
015 */
016 #include <stdio.h>
017 #include <stdlib.h>
018
019 #include "figureSmallestExpend.h"
020
021 int main(void) {
022 int numFruits, count;
023 numFruits = count = 0;
024 int *numFruit;
025 numFruit = NULL;
026 puts(
027 "Pleause input the number of the fruits-kind AND the number of each one: "); /* prints */
028 scanf("%d", &numFruits);
029 numFruit = (int *) calloc(numFruits, sizeof(int));
030 if (numFruit == NULL) {
031 printf("*************Memerry Error!!!*************");
032 return EXIT_FAILURE;
033 }
034 getchar();
035
036 for (count = 0; count < numFruits; count++) {
037 *(numFruit + count) = getchar() - 48;
038 getchar();
039 }
040 /*printf("\n");
041 for (count = 0; count < numFruits; count++) {
042 printf("%d,", *(numFruit + count));
043 }
044 printf("\n");
045 */
046
047 printf("The smallest expend is:%d .\n", figureSmallestExpend(numFruit,
048 numFruits));
049 system("pause");
050 return EXIT_SUCCESS;
051 }
052
053
054 /*
055 * figureSmallestExpend.h
056 *
057 * Created on: 2008-9-4
058 * Author: WuYimin
059 */
060
061 #ifndef FIGURESMALLESTEXPEND_H_
062 #define FIGURESMALLESTEXPEND_H_
063
064 /*
065 *figure out the Smallest expend to move all of the fruits
066 *@args:int *--the array which use to record the number of every one fruit
067 *@args:int --the total number of the kinds of the fruits
068 *@return:int --the object--the smallest expend.
069 */
070 int figureSmallestExpend(int *, int);
071
072 #endif /* FIGURESMALLESTEXPEND_H_ */
073
074
075
076
077
078 /*
079 * figureSmallestExpend.c
080 *
081 * Created on: 2008-9-4
082 * Author: WuYimin
083 */
084 /*
085 *figure out the Smallest expend to move all of the fruits
086 *@args:int *--the array which use to record the number of every one fruit
087 *@args:int --the total number of the kinds of the fruits
088 *@return:int --the object--the smallest expend.
089 */
090
091 #include "figureSmallestExpend.h"
092
093 int figureSmallestExpend(int *weights, int kinds) {
094 int smallestExpend = 0;
095 int count = 2;
096 int *temp;
097 int tempswap;
098
099 if (kinds == 1)
100 return smallestExpend;
101 if (kinds == 2) {
102 smallestExpend += *weights + *(weights + 1);
103 return smallestExpend;
104 } else {
105 for (count = 2, temp = weights; count < kinds; count++) {
106 if (*temp > *(weights + count))
107 temp = weights + count;
108 else
109 continue;
110 }
111 tempswap = *temp;
112 *temp = *weights;
113 *weights = tempswap;
114
115 for (count = 2, temp = weights + 1; count < kinds; count++) {
116 if (*temp > *(weights + count))
117 temp = weights + count;
118 else
119 continue;
120 }
121 tempswap = *temp;
122 *temp = *(weights + 1);
123 *(weights + 1) = tempswap;
124 }
125
126 smallestExpend = *(weights + 1) = *weights + *(weights + 1);
127 smallestExpend = smallestExpend + figureSmallestExpend(weights + 1, kinds
128 - 1);
129 return smallestExpend;
130 }
所有评论，共0条：( 我也来说两句)