基本算法和经典问题选讲 中国科学技术大学 袁平波
基本算法和经典问题选讲 中国科学技术大学 袁平波
主要内容 穷举法 贪心法 回溯法
主要内容 • 穷举法 • 贪心法 • 回溯法
一、穷举法（枚举法） 列出问题的全部可能解，然后找到最佳解 例： 设有A、B、C、D四个数都在1~16范围 内。要求打印出四个数都不相同时，其和 为34的所有值。 算法分析： 最直接的想法是设置A、B、C、D四个变 量，都从1至16循环。需要164次。且循环 中还必须判四数有所重复的情况
一、穷举法（枚举法） • 列出问题的全部可能解，然后找到最佳解 • 例： 设有A、B、C、D四个数都在1～16范围 内。要求打印出四个数都不相同时，其和 为34的所有值。 • 算法分析： 最直接的想法是设置A、B、C、D四个变 量，都从1至16循环。需要164次。且循环 中还必须判四数有所重复的情况
加上一定的限制条件 设A<B<C<D,A的初值为1，B的初值为 A+1,C的初值为B+1,D的初值为C+1。 每个循环的终值也可以算出： A+A+1+A+2+A+3=34 A=7 1+B+B+1+B+2=34 B=10 1+2+C+C+1=34 C=15 1+2+3+D=34 D=28
加上一定的限制条件 • 设A<B<C<D，A的初值为1，B的初值为 A＋1，C的初值为B＋1，D的初值为C+1。 • 每个循环的终值也可以算出： A + A+1 + A+2 + A+3 = 34 A=7 1 + B + B+1 + B+2 = 34 B=10 1 + 2 + C + C+1 = 34 C＝15 1＋2＋3＋D＝34 D＝28
算法实现函数 void fournums() int a,b,c,d for (a 1;a<-7;a++) for(b=a+1;b<=l0;b++) for(c=b+1;c<=15;c++) for(d=c+1,d<=28,d++) if (a+b+c+d ==34)cout <<a,b,c,d
算法实现函数 void fournums() { int a, b, c, d ; for (a = 1; a<=7; a++) for (b = a+1; b<=10; b++) for (c = b+1; c<=15; c++) for (d = c+1; d<=28; d++) if (a+b+c+d == 34) cout <<a ,b,c,d }