递归算法的执行过程分两个阶段:_________________递推和回归

 

 

问题的最优解包含其子问题的最优解是什么性质_________最优子结构性质

 

 

将一个问题分成大小相等的k个子问题的处理方法是行之有效的，这是什么思想________________________平衡（balancing）子问题的思想

 

快速排序的运行时间与什么有关____________划分是否对称

 

Strassen矩阵乘法中为了降低时间复杂度，做出什么改进_______减少乘法的次数

 

 

 

 

 

 

 

分治法编程：改写二分搜索算法。

设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

#include <stdio.h>
#include <stdlib.h>

int search(int a[],int length,int x)
{
 int i=0,j=0;
 int detection=-1;
 int top=length-1;
 int middle=0;
 int low=0;
 
 while(low<=top)
 {
 middle=(low+top)/2;
 if(a[middle]==x){
 detection=middle;
 }
 if(a[middle]<x)
 {
 low=middle+1;
 }
 else{
 top=middle-1;
 }
 
 }
 if(detection==-1)
 {
 i=top;
 j=low;
 }
 else{
 i=detection;
 j=i;
 }
 
 printf("i的值为：%d\nj的值为：%d\n",i,j);
 return 0;
}

int main()
{
 int h[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
 int length = sizeof(h) / sizeof(int);
 search(h,length,12);
 system("pause");
 
}

 

 

分治法编程：设集合R={r1,r2,...,rn}是要进行排列的n个元素，其中r1,r2,...,rn可能相同。 试着设计一个算法，列出R的所有不同排列。 即，给定n以及待排的n个可能重复的元素。计算输出n个元素的所有不同排列。

写出完整代码，并给出测试用例和测试结果。

输入样例
        输入：
4 
aacc 
输出：
aacc 
acac 
acca 
caac 
caca 
ccaa 
6

 

#include<stdio.h>
#include<string.h>
int count=0;
void swap(char &a,char &b)
{
 char temp;
 temp=a;
 a=b;
 b=temp;
}
int finish(char list[],int k,int i)
{//第i个元素是否在前面元素[k...i-1]中出现过
 if(i>k)
 {
 for(int j=k;j<i;j++)
 if(list[j]==list[i])
 return 0; 
 }
 return 1;
}
void perm(char list[],int k,int m)
{
 if(k==m)    //当只剩下一个元素时则输出 
 {
 count++;
 for(int i=0;i<=m;i++)
 printf("%c",list[i]);
 putchar('\n');
 }
 for(int i=k;i<=m;i++)  //还有多个元素待排列，递归产生排列
 {
 if(finish(list,k,i))
 {
 swap(list[k],list[i]);
 perm(list,k+1,m);
 swap(list[k],list[i]);
 }
 } 
}
int main()
{
 int i,n;
 printf("请输入元素个数:\n"); 
 scanf("%d",&n);
 printf("请输入待排列的元素:\n");
 getchar();
 char *a=new char[n];
 for(i=0;i<n;i++)
 scanf("%c",&a[i]);
 printf("所有不同排列为:\n");
 perm(a,0,n-1);
 printf("排列总数为：%d\n",count);
 return 0;
} 

 

 

贪心法编程：汽车加油问题

一辆汽车加油满后可行驶n千米。旅途中有k个加油站（不包含汽车的出发点）。假如在出发时已加满油，请设计一个算法，使汽车在旅途中加油次数最少，并给出加油的地点。

写出完整代码、测试用例和测试结果。

 

#include<stdio.h>
#define M 100
int main(){
 int stations[M];//八个间距
 int ins; //油箱满的时候可以走的距离
 int num;//中间加油站的数量
 int i;
 int all=0;//总的加油次数
 int lv;//油箱中的油量可以走的距离 
 
 
 printf("请输入加油站的距离和数量\n");
 scanf("%d%d",&ins,&num);
 lv=ins;//油量赋初值
 
 printf("请输入加油站间的距离\n");
 for(i=0;i<num+1;i++){
  scanf("%d",&stations[i]);
 }
 
 printf("加油站间的距离分别为：\n");
 for(i=0;i<num+1;i++){
  printf("%d  ",stations[i]);
 }
 puts("");
 
 
 for(i=0;i<num+1;i++){//如果油量可以支撑下一段路，则继续走
 
 if(stations[i]>ins) {
 printf("汽车不可能达到终点站");
 return 0;
 }
 
 if(lv>=stations[i]){
 lv-=stations[i];
 }
 
 else {  //否则加满油
 lv=ins-stations[i];
 all++;
 printf("汽车在第%d站加了油\n",i);
 }
 }
 
 printf("需要加油的总的加油站数量\n");
 printf("%d\n",all);//输出总的加油次数
}

 

大学算法分析与设计复习总结：：

https://blog.****.net/wwj_748/article/details/9040635