データを配列に入れてbox=[1,2,3,・・・]として最大値を求めるプログラムを作成する。
1.データ数が1のとき、box[0]が最大値となる
2.データ数が2のとき、box[0]をグループ1としbox[1]をグループ2として、グループ1の最大値とグループ2の最大値を比較し
大きい方がデータの最大値となる。
3.データ数が4のとき box[0]～box[1]をグループ1としbox[2]～box[3]をグループ2としてグループ1の最大値とグループ2の最大値を比較し
大きい方がデータの最大値となる。
4.データ数が8のとき、box[0]～box[3]をグループ1としbox[4]～box[7]をグループ2としてグループ1の最大値とグループ2の最大値を比較し
大きい方がデータの最大値となる。
5.データ数が16のとき、box[0]～box[7]をグループ1としbox[8]～box[16]をグループ2としてグループ1の最大値とグループ2の最大値を比較し
大きい方がデータの最大値となる。
6.データ数が32のとき、box[0]～box[15]をグループ1としbox[16]～box[32]をグループ2としてグループ1の最大値とグループ2の最大値を比較し
大きい方がデータの最大値となる。
このようにn(データが2のべき乗)のときbox[[0]～box[(n/2)-1]をグループ1としbox[n/2]～box[n-1]をグループ2
としてグループ1の最大値とグループ2の最大値を比較し
大きい方がデータの最大値となる。
最小値も同様な考え方でできる。
プログラムのソースは以下
//最大値を求める(データの数が2のべき乗限定)
#include<stdio.h>
#include<math.h>
int min(int *, int);
int main()
{
int c[] = {1,2,3,4,5,600,7,8,9,10,11,12,16,14,15,13,2,18,1889,20,21,22,23,24,25,26,27,28,29,30,31,32};
printf("最大値:%d\n", min(c, 7));
return 0;
}
//最大値を求める
int min(int *m, int n)
{
if(n==2){return m[0];}
else if(n==3){return (min(m, 2) < min(m+1, 2)) ? min(m+1, 2) :min(m, 2);}
else if(n==4){return (min(m, 3) < min(m+2, 3)) ? min(m+2, 3) :min(m, 3);}
else if(n==5){return (min(m, 4) < min(m+4, 4)) ? min(m+4, 4) :min(m, 4);}
else if(n==6){return (min(m, 5) < min(m+8, 5)) ? min(m+8, 5) :min(m, 5);}
else {return (min(m, 6) < min(m+16, 6)) ? min(m+16, 6) :min(m, 6);}
}
これを実行すると
C:\>0515.exe
最大値:1889
これを改造してデータをscanfで読み込むようにする。
プログラムのソースは以下
//最大値と最小値を求める
//データは2のべき乗に限られる
//scanfでデータを入力する
//最大値と最小値を求める関数の第2引数にデータの個数を底2の対数をとって2を足した値を渡す
#include<stdio.h>
#include<math.h>
int max_of_array(int *, double);
int min_of_array(int *, double);
#define N 400//入力するデータの数は400以下
int main()
{
int kk;
int box[N],i;
double pp,n;
printf("データの数を入力せよ>>");
scanf("%d",&kk);
printf("データを1つずつ入力せよ\n");
pp=(log(kk)/log(2));
for(i=0;i<kk;i++){scanf("%d",&box[i]);}
printf("%dは2の%lf乗である\n",kk,pp);
n=pp+2;
printf("第2引数n=%lf\n",n);
printf("最大値:%d\n", max_of_array(box, n));
printf("最小値:%d\n", min_of_array(box, n));
return 0;
}
//最大値を求める
int max_of_array(int *m, double n)
{
int g;
if(n==2){return m[0];}
else {g=pow(2,(n-3));
return (max_of_array(m, n-1) < max_of_array(m+g, n-1)) ? max_of_array(m+g, n-1) :max_of_array(m, n-1);}
}
//最小値を求める
int min_of_array(int *m, double n)
{
int g;
if(n==2){return m[0];}
else {g=pow(2,(n-3));
return (min_of_array(m, n-1) > min_of_array(m+g, n-1)) ? min_of_array(m+g, n-1) :min_of_array(m, n-1);}
}
これを実行すると
C:\>0515.exe
データの数を入力せよ>>16
データを1つずつ入力せよ
3
53
24
65
33
55
33
75
33
44
663
24
-8
-8
55
44
16は2の4.000000乗である
第2引数n=6.000000
最大値:663
最小値:-8
この結果は正しい。