分治算法代码
A. c语言中用分治法求大数相乘的代码
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define N 100//最大100位
/* 函数声明 */
void calc1(char* str1,int len1,int* tmp,int m);
void accumulate(int cnt,int* res,int res_len,int* tmp,int tmp_len);
char* bignum_multi(char* str1,int len1,char* str2,int len2,char* result,int len);
int main()
{
int i,j;
/* 获取计算数据(可以从文件中读取) */
char str1[N]={NULL};
char str2[N]={NULL};
char result[N*N]={NULL};
printf("Input Num1: \n");
scanf("%s",str1);
fflush(stdin);
printf("Input Num2: \n");
scanf("%s",str2);
/* 计算两个字符串的长度,及存储结果所需要的空间 */
int len1=strlen(str1),len2=strlen(str2);
int len=len1+len2;
/* 计算并输出计算结果 */
printf("The result is: %s\n",bignum_multi(str1,len1,str2,len2,result,len));
return 0;
}
/*===============================================================
调用calc1和accumulate函数计算大数相乘
===============================================================*/
char* bignum_multi(char* str1,int len1,char* str2,int len2,char* result,int len)
{
int i,j,m=0,cnt=0,*tmp,*res;
/* 分配临时结果的存放空间 */
tmp=(int*)malloc((len1+1)*sizeof(int));
res=(int*)malloc(len*sizeof(int));
/* 初始化两个数组 */
for(i=0;i<len1;i++)
tmp[i]=0;
for(j=0;j<len;j++)
res[j]=0;
for(i=len2-1;i>=0;i--)
{
/* 获取乘数中第i位的值 */
m=str2[i]-'0';
/* 计算被乘数与第i位的乘积,结果保存在tmp整型数组中 */
calc1(str1,len1,tmp,m);
/* 将tmp数组中的值加到res数组中 */
cnt++;
accumulate(cnt,res,len,tmp,len1+1);
}
/* 将整形数组res中的值转化成字符串存入result中 */
i=0;j=0;
/* 去掉res中第一个非零数字前的零 */
while(res[i++]==0);
for(m=i-1;m<len;m++,j++)
result[j]=res[m]+0x30;
result[j]='\0';
free(tmp);
free(res);
return result;
}
/*===============================================================
计算被乘数与乘数的某一位的乘积
===============================================================*/
void calc1(char* str1,int len1,int* tmp,int m)
{
/* d两个位的乘积结果,remainder余数,carry进位 */
int i,d=0,remainder=0,carry=0;
/* 从被乘数字符串'\0'的前一位算起 */
for(i=len1-1;i>=0;i--)
{
d=str1[i]-'0';
d*=m;
remainder=(d+carry)%10;
carry=(d+carry)/10;
tmp[i+1]=remainder;
}
if(carry)
tmp[0]=carry;
else
tmp[0]=0;
}
/*===============================================================
将被乘数与乘数中一位数字的乘积结果计入res数组中
===============================================================*/
void accumulate(int cnt,int* res,int len,int* tmp,int len1)
{
int m=0,n=0,i,k,remainder=0;
static int carry=0;
for(k=len1-1,i=0;k>=0;k--,i++)
{
m=tmp[k];
n=res[len-cnt-i];
if(m+n+carry>=10)
{
remainder=(m+n+carry)%10;
carry=1;
}
else
{
remainder=m+n+carry;
carry=0;
}
res[len-cnt-i]=remainder;
}
}
B. c语言算法。分治法，金块问题。
int &fmin表示形参的【引用】声明，&是【引用操作符】，不是指针的地址操作符，都可以表示指向， int &fmin“参数类型 &形参”实际上相当于“int &fmin=min”，“参数类型 &形参=实参”
被引用的形参fmin与其对应的实参min代表同一变量，可以互换，代替实参进行同样的操作，可理解为实参的别名
”同样是int类型的虚参，为啥跟i，j不是一个待遇“
这句话的理解不对
在maxmin(int i,int j,int &fmax,int &fmin){......}中，i、j是maxmin()函数的形参（虚参）
在int main (){ int n,i,j,max,min;.......}中，i、j是主函数main（）的参数，当它们用在maxmin()函数的函数头，作为maxmin()函数的参数，理解为maxmin()函数的实参（是maxmin()函数的实参），是函数形参的具体赋值，
所以通常只有在主函数main（）中才可以看到有实参的函数头（实参值调用形式）或无实参的空函数头
只有在主函数中看到其它所有函数的实参
C. C++算法，分治法实现归并
参考如下
//分治法实现归并排序
#include <iostream>
using namespace std;
#define SIZE 10
void merge(int array[],int first,int mid,int last) //合并
{
int new_arr[SIZE],i,j,k=first;
memset(new_arr,0,SIZE);
for (i = first,j = mid + 1;(i <= mid)&&(j <= last);)
{
if(array[i] <= array[j])
new_arr[k++] = array[i++];
else
new_arr[k++] = array[j++];
}
if(i <= mid)
for(;i <= mid;i++)
new_arr[k++] = array[i];
if(j <= last)
for(;j <= last;j++)
new_arr[k++] = array[j];
for(int p = first;p <=last;p++) //将排好顺序的元素放回原数组【注意：p的范围为每个小分支中的元素，而非整个0到sizeof(arr)/sizeof(int)】
array[p]=new_arr[p];
}
void merge_sort(int array[],int first,int last)//归并排序
{
int mid = 0;
if(first<last)
{
mid = (first + last)/2;
merge_sort(array, first,mid);
merge_sort(array, mid+1,last);
merge(array,first,mid,last);
}
}
int main()
{
int arr[SIZE]={9,3,5,6,8,7,0,2,1,4};
merge_sort(arr,0,9);
for(int i = 0;i < SIZE;i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
D. 算法导论，分治法求最大子数组，求一个c语言代码
这题的思想是书上的（《算法导论》），代码当然也是按照书上伪码写出的；
#include<stdio.h>
intFind_Max_Crossing_SubArray(intA[],intlow,intmid,inthigh)
{
intleft_sum=-0xff;
intsum=0;
for(inti=mid;i>=low;i--)
{
sum+=A[i];
if(sum>left_sum)
{
left_sum=sum;
}
}
intright_sum=-0xff;
sum=0;
for(intj=mid+1;j<=high;j++)
{
sum+=A[j];
if(sum>right_sum)
{
right_sum=sum;
}
}
returnleft_sum+right_sum;
}
intFind_Maximum_SubArray(intA[],intlow,inthigh)
{
intleft_sum,right_sum,cross_sum;
if(high==low)
{
returnA[low];
}
else
{
intmid=(low+high)/2;
left_sum=Find_Maximum_SubArray(A,low,mid);
right_sum=Find_Maximum_SubArray(A,mid+1,high);
cross_sum=Find_Max_Crossing_SubArray(A,low,mid,high);
if(left_sum>=right_sum&&left_sum>=cross_sum)
{
returnleft_sum;
}
elseif(right_sum>=left_sum&&right_sum>=cross_sum)
{
returnright_sum;
}
else
{
returncross_sum;
}
}
}
intmain()
{
intA[100];
intn;
printf("Pleaseinputthenumberofnumbers:");
scanf("%d",&n);
for(inti=0;i<n;i++)
{
scanf("%d",&A[i]);
}
printf("最大子序列的和为：%d",Find_Maximum_SubArray(A,0,n-1));
return0;
}
E. 找最大最小元素的分治算法 C语言代码 急
while
(true)
{
double
num1,num2,num3;
int
flag;
printf("请输入第1个数：");
flag=scanf("%lf",&num1);
printf("请输入第2个数：");
flag=scanf("%lf",&num2);
printf("请输入第3个数：");
flag=scanf("%lf",&num3);
fflush(stdin);
if(flag==0)
{
printf("对不起，你的输入有误，请重新输入！！！\n");
system("pause");
return;
}
int
max=0;
if(max<num1)
{
max=num1;
if(max<num2)
{
max=num2;
if(max<num3)
{
max=num3;
}
}
}
printf("%.2lf、%.2lf、%.2lf这三个数，最大的数是%.2lf\n",num1,num2,num3,max);
printf("是否继续，继续请按Y，不继续，按任意键退出！\n");
char
choice=getchar();
if(choice!='y'&&choice!='Y')
{
printf("退出成功！\n");
break;
}
}
system("pause");
F. 分治算法的应用实例
下面通过实例加以说明： 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。
另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。
假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法求出。算法如下：
void maxmin1(int A[],int n,int *max,int *min)
{ int i;
*min=*max=A[0];
for(i=0;i <= n;i++)
{ if(A[i]> *max) *max= A[i];
if(A[i] < *min) *min= A[i];
}
}
上面这个算法需比较2(n-1)次。能否找到更好的算法呢？我们用分治策略来讨论。
把n个元素分成两组：
A1={A[1],...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]}
分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。
例如有下面一组元素：-13，13，9，-5，7，23，0，15。用分治策略比较的算法如下：
void maxmin2(int A[],int i,int j,int *max,int *min)
/*A存放输入的数据，i，j存放数据的范围，初值为0，n-1，*max,*min 存放最大和最小值*/
{ int mid,max1,max2,min1,min2;
if (j==i) {最大和最小值为同一个数;return;}
if (j-1==i) {将两个数直接比较，求得最大会最小值；return；}
mid=(i+j)/2;
求i~mid之间的最大最小值分别为max1，min1;
求mid+1~j之间的最大最小值分别为max2，min2;
比较max1和max2，大的就是最大值;
比较min1和min2，小的就是最小值;
} 题目：在一个(2^k)*(2^k)个方格组成的棋盘上，有一个特殊方格与其他方格不同，称为特殊方格，称这样的棋盘为一个特殊棋盘。我们要求对棋盘的其余部分用L型方块填满（注：L型方块由3个单元格组成。即围棋中比较忌讳的愚形三角，方向随意），且任何两个L型方块不能重叠覆盖。L型方块的形态如下：
题目的解法使用分治法，即子问题和整体问题具有相同的形式。我们对棋盘做一个分割，切割一次后的棋盘如图1所示，我们可以看到棋盘被切成4个一样大小的子棋盘，特殊方块必定位于四个子棋盘中的一个。假设如图1所示，特殊方格位于右上角，我们把一个L型方块（灰色填充）放到图中位置。这样对于每个子棋盘又各有一个“特殊方块”，我们对每个子棋盘继续这样分割，直到子棋盘的大小为1为止。
用到的L型方块需要（4^k-1)/3 个，算法的时间是O（4^k)，是渐进最优解法。
本题目的C语言的完整代码如下（TC2.0下调试），运行时，先输入k的大小，(1<=k<=6)，然后分别输入特殊方格所在的位置(x,y), 0<=x,y<=(2^k-1)。 #include<stdio.h>//#include<conio.h>//#include<math.h>inttitle=1;intboard[64][64];voidchessBoard(inttr,inttc,intdr,intdc,intsize){ints,t;if(size==1)return;t=title++;s=size/2;if(dr<tr+s&&dc<tc+s)chessBoard(tr,tc,dr,dc,s);else{board[tr+s-1][tc+s-1]=t;chessBoard(tr,tc,tr+s-1,tc+s-1,s);}if(dr<tr+s&&dc>=tc+s)chessBoard(tr,tc+s,dr,dc,s);else{board[tr+s-1][tc+s]=t;chessBoard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s&&dc<tc+s)chessBoard(tr+s,tc,dr,dc,s);else{board[tr+s][tc+s-1]=t;chessBoard(tr+s,tc,tr+s,tc+s-1,s);}if(dr>=tr+s&&dc>=tc+s)chessBoard(tr+s,tc+s,dr,dc,s);else{board[tr+s][tc+s]=t;chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}voidmain(){intdr=0,dc=0,s=1,i=0,j=0;printf(printinthesizeofchess:
);scanf(%d,&s);printf(printinspecalpointx,y:
);scanf(%d%d,&dr,&dc);if(dr<s&&dc<s){chessBoard(0,0,dr,dc,s);for(i=0;i<s;i++){for(j=0;j<s;j++){printf(%4d,board[i][j]);}printf(
);}}elseprintf(thewrongspecalpoint!!
);getch();}
G. 分治算法中排序的完整代码
快速排序
#include<windows.h>
#include<time.h>
#include<stdio.h>
#define MAX 10
void InitData(int a[],int len)
{//随机初始化待排序数据
int i;
srand(time(NULL));
for(i=0;i<len;i++) a[i]=rand()%1000;//随机初始化待排序数据
}
void Print(int a[],int from,int to)
{//输出a[from]到a[to]范围内所有数据，并换行
int i;
for(i=0;i<from;i++) printf(" ");//控制对齐，看出解决子问题的顺序
for(i=from;i<=to;i++) printf("%4d",a[i]);
printf("\n");
}
int part(int A[ ], int from, int to)
{int i=from+1, j=to, temp;
while( i<=j){ while(i<=to && A[i]<=A[from]) i++;
while(j>=from && A[j]>A[from]) j--;
if(i<j) {temp=A[i];A[i]=A[j];A[j]=temp;} //A[j]与A[j]交换
}
temp=A[j]; A[j]=A[from]; A[from]=temp;//A[j]与A[from]交换
return j;
}
void QuickSort(int A[ ], int from, int to) //快速排序的分治思想表达
{
if(from<to){ int position=part(A, from, to);
QuickSort(A,from,position-1);
QuickSort(A, position+1, to);
}
Print(A,from,to);
}
void main(void)
{
int A[MAX];
InitData(A,MAX);
Print(A,0,MAX-1);
QuickSort(A,0,MAX-1);
getch();
}
归并排序
#include<windows.h>
#include<stdio.h>
#define MAX 17
void InitData(int a[],int len)
{int i;
for(i=0;i<len;i++) a[i]=rand()%1000;//随机初始化待排序数据
}
void Print(int a[],int from,int to)
{
int i;
for(i=0;i<from;i++) printf(" ");//控制对齐，看出解决子问题的顺序
for(i=from;i<=to;i++) printf("%4d",a[i]);
printf("\n");
}
void Merge(int A[ ], int from, int to)
{
int *t=(int *)malloc(sizeof(int)*(to-from+1));
int i=from, mid=(to+from)/2, j=mid+1,k=0;
if(from>=to) return ;
Merge (A, from, mid);
Merge (A, mid+1, to); /*递归解决2个子问题*/
while(i<=mid && j<=to)
if(A[i]<A[j]) t[k++]=A[i++];
else t[k++]=A[j++];
while(i<=mid) t[k++]=A[i++];
while(j<=to) t[k++]=A[j++];
i=from;k=0;
while(i<=to) A[i++]=t[k++];//合并两个有序子表，即分别A[from~mid],A[mid+1~to];
//if(to-from>0)
Print(A,from,to); //合并子问题之后，将其打印出来
}
void main(void)
{
int a[MAX];
InitData(a,MAX);
Print(a,0,MAX-1);
Merge(a,0,MAX-1);
getch();
}
H. 分治算法
算法步骤：
1 ：从左上角起，给棋盘编号（1，1），（1，2），。。。。。。（8，8），计为集合qp。tracks记录走过的每个点. （可以想象为坐标（x,y））
2：设起点为（1，1），记为 当前位置 cp，
3：搜索所有可走的下一步，根据“马行日”的走步规则，可行的点的坐标是x坐标加减1，y坐标加减2，
或是x加减2，y加减1； （例如起点（1，1），可计算出（1+1，1+2），（1+1，1-2），（1-1，1+2），（1-1，1-2），（1+2，1+1），（1+2，1-1），（1-2，1+1），（1-2，1-1） 共8个点）， 如果没有搜到可行点，程序结束。
4：判断计算出的点是否在棋盘内，即是否在集合qp中；判断点是否已经走过，即是否在集合tracts中，不在才是合法的点。（在上面的举例起点（1，1），则合法的下一步是（2，3）和 （3，2））
5：将前一步的位置记录到集合tracts中，即tracts.add（cp）；选择一个可行点，cp=所选择点的坐标。
6：如果tracts里的点个数等于63，退出程序，否则回到步骤3继续执行。
I. 求用分治算法 二进制数大整数乘法
设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。
我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)。
由此，X=A2n/2+B ，Y=C2n/2+D。这样，X和Y的乘积为：
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)
如果按式(1)计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，
以及3次不超过n位的整数加法(分别对应于式(1)中的加号)，此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数，由此可得T(n)=O(n2)。因此，用(1)式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性，必须减少乘法次数。为此我们把XY写成另一种形式:
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)
虽然，式(3)看起来比式(1)复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D-C))，6次加、减法和2次移位。用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式(3)，并考虑到X和Y的符号对结果的影响，我们给出大整数相乘的完整算法MULT如下:
function MULT(X，Y，n); {X和Y为2个小于2n的整数，返回结果为X和Y的乘积XY}
begin
S:=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}
X:=ABS(X);
Y:=ABS(Y); {X和Y分别取绝对值}
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A:=X的左边n/2位;
B:=X的右边n/2位;
C:=Y的左边n/2位;
D:=Y的右边n/2位;
ml:=MULT(A,C,n/2);
m2:=MULT(A-B,D-C,n/2);
m3:=MULT(B,D,n/2);
S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
代码的实现
[cpp] view plainprint?
/************************************************************************/
//函数功能：分治法求两个N为的整数的乘积
//输入参数：X,Y分别为两个N为整数
//算法思想：
//时间复杂度为：T(n)=O(nlog3)=O(n1.59)
/************************************************************************/
#define SIGN(A) ((A > 0) ? 1 : -1)
int IntegerMultiply(int X, int Y, int N)
{
int sign = SIGN(X) * SIGN(Y);
int x = abs(X);
int y = abs(Y);
if((0 == x) || (0 == y))
return 0;
if (1 == N)
return x*y;
else
{
int XL = x / (int)pow(10., (int)N/2);
int XR = x - XL * (int)pow(10., N/2);
int YL = y / (int)pow(10., (int)N/2);
int YR = y - YL * (int)pow(10., N/2);
int XLYL = IntegerMultiply(XL, YL, N/2);
int XRYR = IntegerMultiply(XR, YR, N/2);
int XLYRXRYL = IntegerMultiply(XL - XR, YR - YL, N/2) + XLYL + XRYR;
return sign * (XLYL * (int)pow(10., N) + XLYRXRYL * (int)pow(10., N/2) + XRYR);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int x = 1234;
int y = 4321;
cout<<"x * y = "<<IntegerMultiply(x, y, 4)<<endl;
cout<<"x * y = "<<x*y<<endl;
return 0;
}
J. 汉诺塔分治算法代码解释一下，谢谢！
递归算法是计划算法的，不用钻进去函数里面的。
设f(n, a, b,c) 表示 把n个盘从a移到c 借助b ，它等于三个步骤
1.n-1个盘从a移到b
2 1个盘从a移到c
3 n-1个盘从b移到c
看第一个步骤，n-1个盘从a移到b，设为g(n-1,a,c,b),它又等于三个步骤
n-2个盘从a移到c
1个盘从a移到b
n-1个盘从c移到b
这三个步骤恰恰是盘子为n-1时，从a移到b借助c的步骤，就是说，这三个步骤等于f(n-1,a,c,b)
所以g(n-1,a,c,b)=f(n-1,a,c,b),进而推的
f(n, a, b,c) = ( f(n-1, a,c,b) , f(1, a, b,c), f(n-1, b,a,c))
自己参悟吧，很简单的。