‘壹’ 用c语言利用分治法求一组数据中最大的两个数和最小的两个数
#include <stdio.h>
main()
{
int a[10]={1,3,5,7,9,10,8,6,4,2};
int i,max1=0,max2=0,min1=0,min2=0;
for(i=0;i<10;i++)
{
if(a[max1]<a[i])
max1=i;
if(a[min1]>a[i])
min1=i;
}
if(max1==0)
max2=1;
if(min1==0)
min2=1;
for(i=0;i<10;i++)
{
if(i==max1||i==min1)
continue;
if(a[max2]<a[i])
max2=i;
if(a[min2]>a[i])
min2=i;
}
printf("max1=%d\nmax2=%d\nmin1=%d\nmin2=%d\n",a[max1],a[max2],a[min1],a[min2]);
}
‘贰’ 求大佬看道c语言算法问题：用分治法求数组元素最大最小值
请参照快排的方式 最大/小使用全局变量
‘叁’ 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;
}
}
‘肆’ c语言：采用分治法递归求含n个数的某个序列的最大元素和次大元素。
high -low 为奇数，这个mid是小数。
（1）数组个数为n，还用a[n]
（2）还不如直接用个for循环，将max=0
#include <stdio.h>
#define N 21
int max(int a,int b){
if(a>b)
return a;
return b;
}
int getM(int * a,int l,int u){
if(u==l)
return a[u];
else{
return max(getM(a,l,(u+l)/2),getM(a,(u+l)/2+1,u) );
}
}
int main()
{
int a[N]={1,2,3,4,5,6,7,8,9,21,11,12,13,14,15,16,17,18,19,20,17};
printf("max=%d",getM(a,0,N-1));
return 0;
}
(4)c语言分治扩展阅读：
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。
n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可。
而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
‘伍’ 一个C语言经典的分治问题
#include<stdio.h>
intpartition(inta[],intlow,inthigh)
{
intpivot=a[low];
inti=low;
intj=i+1;
for(;j<=high;++j)
{
if(a[j]<pivot)
{
++i;
inttemp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
inttemp=a[i];
a[i]=pivot;
a[low]=temp;
returni;
}
intfindKth(inta[],intlow,inthigh,intk)
{
if(low==high)
returna[low];
intr=partition(a,low,high);
inti=r-low+1;
if(i==k)
returna[r];
elseif(i<k)
findKth(a,r+1,high,k-i);
else
findKth(a,low,r-1,k);
}
intmain()
{
inta[]={3,6,5,56,48,1,34,78,99,0};
for(inti=1;i<=10;++i)
{
intresult=findKth(a,0,9,i);
printf("%dth->%d ",i,result);
}
return1;
}
《 算法导论》 中位数和顺序统计量 第二节有详细说明
‘陆’ C语言用分治算法求一组数中第二小的数
#include<stdio.h>
int main()
{
double arr[10],g;
printf("共输入十个数,不满意可以调\n");
for (int a=0;a<=9;a++)
{
printf("输入数组中第[%d]个数:",a);
scanf("%lf",(arr+a));
}
for (int x=1;x<10;x++)
{
for (int k=0;k<=8;k++)
{
if (*(arr+k)>*(arr+k+1))
{
g=*(arr+k);
*(arr+k)=*(arr+k+1);
*(arr+k+1)=g;
}
}
}
printf("第二小的数是:%lf",*(arr+1));
}
‘柒’ 分治法c语言求最大最小值
1、分治法不是用来求最大值最小值的。在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)。
分治法的精髓：
分--将问题分解为规模更小的子问题；
治--将这些规模更小的子问题逐个击破；
合--将已解决的子问题合并，最终得出“母”问题的解。
2、求数组中的最大值和最小值，一般使用假设法，即假设数组的第1个元素为最大值，同时也是最小值，然后遍历数组，找到最大值和最小值。示例如下:
#include<stdio.h>
intmain()
{
inta[]={1,2,3,4,5,6,7,8,9,10};
intmax,min;
max=min=a[0];//假设第1个元素即是最大值也是最小值。
intmax_pos=0,min_pos=0;
//遍历数组，找出数组a中的最大数和最小数
for(intinx=0;inx!=sizeof(a)/sizeof(int);++inx){
if(a[inx]>max)max=a[inx],max_pos=inx;
elseif(a[inx]<min)min=a[inx],min_pos=inx;
}
printf("最大数:%d 最小数:%d ",max,min);
return0;
}