三、贪心算法

1、找零钱

#include <stdio.h>
int a[7]={100,50,20,10,5,2,1},ns[7];
void main()
{/**********  Begin  **********/int n;scanf("%d",&n);while(n){for(int i=0;i<7;i++){if(n>=a[i]){n=n-a[i];ns[i]++;break;}}}for(int i=0;i<7;i++){printf("%d元 %d张\n",a[i],ns[i]);//cout<<a[i]<<"元 "<<ns[i]<<"张\n";}/**********  End  **********/
}

2、求一个数列的极差

#include <stdio.h>void sort(int *a, int n, int asc) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - 1 - i; j++) {if (asc && a[j] > a[j + 1]) {a[j]=a[j+1]^a[j];a[j+1]=a[j]^a[j+1];a[j]=a[j+1]^a[j];} else if (!asc && a[j] < a[j + 1]) {a[j]=a[j+1]^a[j];a[j+1]=a[j]^a[j+1];a[j]=a[j+1]^a[j];}}}
}
int main() {int i, n, max, min, num;scanf("%d", &num);n = num;int a[num], b[num];for (i = 0; i < num; i++) {scanf("%d", &a[i]);b[i] = a[i];}sort(a, n, 1);while (n > 1) {int m1, m2, nm;m1 = a[0];m2 = a[1];nm = m1 * m2 + 1;a[0] = nm;for (int i = 1; i < n - 1; i++)a[i] = a[i + 1];n--;sort(a, n, 1);max = a[n - 1];}sort(b, num, 0);while (num > 1) {int m1, m2, nm;m1 = b[0];m2 = b[1];nm = m1 * m2 + 1;b[0] = nm;for (int i = 1; i < num - 1; i++)b[i] = b[i + 1];num--;sort(b, num, 0);min = b[num - 1];}printf("Max=max-min=%d-%d=%d\n", max, min, max - min);return 0;
}

3、将真分数用埃及分数之和表示

#include <stdio.h>
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);//辗转相除法 
}
/*设：a>b 1.if a%b==0,b是最大公约数2.a%b!=0,那么a%b的余数的最大公约数就是a和b的反复将较大的除以较小的，然后用余数替换较大的数，直到较小的数=0 
*/ 
int main() {int a, b;scanf("%d %d", &a, &b);printf("%d/%d=", a, b);while (a != 1) {int nb = (b / a) + 1;printf("1/%d+", nb);// 2a = a * nb - b;//3*2 - 5 = 1b = b * nb;// 5*2=10int c = gcd(a, b);a /= c;b /= c;}printf("1/%d\n", b);return 0;
}

4、找到出现最多次数的数

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int a[N],b[N];
int main(){int n;cin>>n;int z=0;for(int i=0;i<n;i++){int num;cin>>num;if(num>=0){a[num]++;z++;}else{b[-num]++;}}int m1=0;for(int i=0;i<N-1;i++){if(m1<a[i])m1=i;if(b[0]<b[i+1])b[0]=i+1;}cout<<"出现次数最多的且最小的数为";if(a[m1]>b[b[0]])cout<<m1;else cout<<-b[0];return 0;
}

5、将给定的整数去掉任意个数字后重新组成最小整数

#include <bits/stdc++.h>
using namespace std;
int main() {/*********  Begin  ********/int n;string s;cin >> s >> n;if (n > s.size()) {return 0;}while (n) {/*2311831:2 3 3>1   del 3 -> 211832:2 2>1     del 2 -> 11833:1 1 8 8>3 del 8 -> 113n=0,break;*/int i;for(i=0;i<s.size()-1&&s[i]<=s[i+1];i++);s.erase(i, 1);n--;}if (s.empty()) {cout << 0 ;}int i;for(i=0;i<s.size();i++){if(s[i]!='0')break;}for(int j=i;j<s.size();j++)cout<<s[j];return 0;/*********  End  ********/
}

GO!