分治演算法代碼
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))
自己參悟吧，很簡單的。