众数分治算法遇到问题与讨论

① 分治算法的解题步骤

分治法解题的一般步骤：
（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;
}