眾數分治演算法遇到問題與討論

① 分治演算法的解題步驟

分治法解題的一般步驟：
（1）分解，將要解決的問題劃分成若干規模較小的同類問題；
（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；
（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。

② 利用分治演算法求解、

在n個元素中找出最大元素和最小元素。我們可以把這n個元素放在一個數組中，用直接比較法求出。演算法如下： void maxmin1(int A[],int n,int *max,int *min) { int i; *min=*max=A[0]; for(i=2;i n;i++) { if(A > *max) *max= A; if(A < *min) *min= A; } } 上面這個演算法需比較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。用分治策略比較的過程如下： 圖中每個方框中，左邊是最小值，右邊是最大值。從圖中看出，用這種方法一共比較了10次，比直接比較法的14次減少4次，即約減少了1/3。演算法如下： void maxmin2(int A[],int i,int j,int *max,int *min) /*A存放輸入的數據，i，j存放數據的范圍，初值為0，n-1，*max,int *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，小的就是最小值; }

③ 眾數問題：給定含有n各元素的多重集合S，每個元素在S中出現次數成為重數。多重集S中重數最大的元素成為眾

#include <stdio.h>
int main()
{
int a[50];
int i,j,maxCount=0,index=0,nCount=0;
int n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(a[j]==a[i])
nCount++;
}
if(nCount>maxCount)
{
maxCount=nCount;
index=i;
}
nCount=0;
}
printf("%d\n%d",a[index],maxCount);
}

④ 眾數問題（非遍歷統計演算法！！！）

遍歷在所難免滴.否則你根本不可能判斷眾數是哪個.至於統計,倒是可以試一試不用.
首先你要先用一個float plural1=0,plural2=0;//用於存放眾數
int plural_times1=0,plural_times2=0;//用於存放眾數出現的次數
先把mode*.in提出來放在一個數組中吧: float[] array_float_in;當然你要盡量大點的數組來存.
然後用一個函數 float* sort(float[]) 將數組排序
現在 現在你可以在數組array_float_in中開始這樣作,找相同的數的段將 plural2=這個段的數,將plural_times2=次數.
比較plura_times2與plura_times1取較大的,存入plural1與plural_times1中,然後是下一段.這樣你可以得到眾數及出現次數.不過這也是變相的統計,只是說把較少的捨去,只有兩個變數來存取.要不你想咋整?

⑤ 使用分治演算法解決的問題具備什麼特徵

分治法能解決的問題一般具有以下幾個特徵：

1、該問題的規模縮小到一定的程度就可以容易的解決。

2、該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。

3、利用該問題分解出的子問題的解可以合並為該問題的解。

4、該問題所分解出的自問題是相互獨立的，即子問題之間不包含子子問題。

(5)眾數分治演算法遇到問題與討論擴展閱讀

思想及策略

分治演算法的設計思想是：將一個難以直接解決的大問題，分割成一些規模小的相同的問題，一邊各個擊破，分而治之。

分治演算法的策略是：對於一個規模為n的問題，若該問題可以容易地解決（比如規模n比較小）則直接解決，否則將其分解成k個規模較小的自問題，這些子問題相互獨立且與元問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。

⑥ 如何使用分治法求眾數

#include<stdio.h>

int largest = 0; //the quantity
int element; //number
int a[10];
int med;

int median(int p,int r)
{
int s = r - p + 1;
if(s%2==0)
return a[s/2-1];
else
return a[s/2];
}

void split(int p,int r,int *p1,int *r1)
{
int i;
for(i=p;i<r;i++)
{
if(a[i]==med)
{
*p1 = i;
break;
}
}
for(i=*p1+1;i<r;i++)
{
if(a[i]!=med)
{
*r1 = i;
break;
}
}
}

void mode(int p,int r)
{
int *p1,*r1;
med = median(p,r);
split(p,r,p1,r1);
if(largest<*r1-*p1+1)
{
largest = *r1-*p1;
element = med;
}
if(*p1-1>largest)
mode(p,*p1-1);
if(r-*r1>largest)
mode(*r1+1,r);
}

void main()
{
int n,i,j;
FILE *fp1,*fp2;
fp1 = fopen("input.txt","r");
if(fp1==NULL)
{
printf("error\n");
return;
}
fscanf(fp1,"%d",&n);
printf("the quantuty of the number %d\n",n);
i = 0;
while(fp1!=NULL)
{
fscanf(fp1,"%d",&a[i]);
i++;
if(i>=n)
break;
}
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
printf("\n");
fclose(fp1);
mode(0,n);
fp2 = fopen("output.txt","w");
if(fp2==NULL)
{
printf("error\n");
}
fprintf(fp2,"%d\n%d",element,largest);
fclose(fp2);
}

⑦ 分治演算法——漢諾塔問題

一、分治演算法概念
      「分而治之」，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合並。

        這個技巧是很多高效演算法的基礎，如排序演算法(快速排序，歸並排序)，傅立葉變換(快速傅立葉變換) 。

        任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於n個元素的排序問題，當n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。而當n較大時，問題就不那麼容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。

二、分治法的設計思想

        將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

三、分治策略

        對於一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。這種演算法設計策略叫做分治法。

四、分治法實現步驟

①分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；②解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；③合並：將各個子問題的解合並為原問題的解。

它的一般的演算法設計模式如下：                                                                                           Divide-and-Conquer(P)                                                                                                          1. if |P|≤n0                                                                                                                               2. then return(ADHOC(P))                                                                                                     3. 將P分解為較小的子問題 P1 ,P2 ,…,Pk                                                                                     4. for i←1 to k                                                                                                                        5. do yi ← Divide-and-Conquer(Pi)  遞歸解決Pi                                                                    6. T ← MERGE(y1,y2,…,yk)  合並子問題                                                                              7. return(T)

五、可使用分治法求解的一些經典問題                                                                             （1）二分搜索 

 （2）大整數乘法

（3）Strassen矩陣乘法

（4）棋盤覆蓋 

 （5）合並排序

（6）快速排序

（7）線性時間選擇

 （8）最接近點對問題

 （9）循環賽日程表

（10）漢諾塔

⑧ 分治演算法的應用實例

下面通過實例加以說明： 給你一個裝有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();}

⑨ 利用分治演算法求解、

對於這種已知不合格硬幣比正常銀幣偏重（或偏輕）的問題，可以用分治法。 以下演算法可以用數學歸納法證明：假設有3枚硬幣，則稱一次，如果a邊重則是a，……，平衡則是c。同理如果有N塊硬幣，我們可以把它分成三堆，稱一次後，這樣問題規模縮小至n/3。重復以上操作，直至稱出。需要次數為log3 n。這是典型的分治法，如果想了解更多，可參考《演算法導論》 謝謝採納我的答案

⑩ 求眾數問題演算法的思路(用遞歸與分治策略)

題目要求輸入若干不超過100的非負整數，輸出眾位數，若有多個，從小到大輸出。
#include <stdlib.h>
#include <string.h>
int main()
{
int n;
scanf("%d",&n);
int i,j,a[100],m,max=0;
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
{
scanf("%d",&m);
a[m]++; //這是程序的巧妙之處，利用數組的下標作為出現數字的保存，而且避免了相同數字的重復記錄。
}
for(i=0;i<100;i++)
for(j=0;j<100;j++)
{
if(a[i]>a[j]&&a[i]>max) //利用變數儲存最大數，想了挺久才想出加上a[i]>max的條件。
max=a[i];
}
for(i=0;i<100;i++)
if(a[i]==max)
printf("%d ",i);
return 0;
}