『壹』 用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;
}