■[プログラミング][C]数列から等差数列を抜き出すCプログラムのサンプル
人力検索はてな どうプログラムを書けば良いか分からなくなったので質問させてく… - 人力検索はてなで質問に答えた際の話題です。
最適化問題は別として、
比較的理論的にとらえやすいアルゴリズムで説明してみます。
[アルゴリズムについて]
質問文での、「0 1 3 4 8 9 10 12 14 15」の数列から
「0 4 8 12」,「1 8 15」,「3 9 15」,
「4 9 14」, 「8 9 10」, 「10 12 14」,「9 12 15」といった、「等間隔な数列を抜き出す」というのは
(※「8 12 14」は等間隔ではないので、「10 12 14」の書き間違いと推測しました。)
「等差数列を抜き出す」行為と定義できると考えられます。
「0 4 8 12」⇒ 「等差 4,初項 0」 (項 An = 0 + 4(n-1) )の等差数列
「1 8 15」 ⇒ 「等差 7, 初項 1」 (項 An = 7 + 1(n-1) )の等差数列
「3 9 15」 ⇒ 「等差 6, 初項 3」 (項 An = 6 + 3(n-1) )の等差数列
「4 9 14」 ⇒ 「等差 5, 初項 4」 (項 An = 5 + 4(n-1) )の等差数列
「8 9 10」 ⇒ 「等差 1, 初項 8」 (項 An = 1 + 8(n-1) )の等差数列
「10 12 14」⇒ 「等差 2, 初項10」 (項 An =10 + 2(n-1) )の等差数列
「9 12 15」 ⇒ 「等差 4, 初項 9」 (項 An = 4 + 9(n-1) )の等差数列
等差数列を、（最適化は別として）理論上わかりやすく抜き出す方法の１つとしては、
・ループで等差と初項を決めて、等差数列の項の条件、
「第n項 = 初項 + 等差×(n-1) 」を立式し、
一致するものを、入力配列の中の、初項以降の部分から走査して
存在を検索する
という方法があります。
質問文の例を見ると、等差と初項がそれぞれ「可変」であるため、
「等差=1,初項=入力数列の1番目」の数列{An=入力数列[0]+1(n-1)}を検索
（A1を入力配列の初項以降から検索,A1見つかったらA2を検索 ...)
「等差=1,初項=入力数列の2番目」の数列{An=入力数列[1]+1(n-1)を検索
（A1を入力配列の初項以降から検索,A1見つかったらA2を検索 ...)
:
「等差=2,初項=入力数列の1番目の数列」{An=入力数列[0]+2(n-1)を検索
（A1を入力配列の初項以降から検索,A1見つかったらA2を検
:というように、
・等差および初項を順番に変化させる
・等差と初項が決まったら、Anを立式し、Anを入力配列の初項以降の部分から検索する。
(nを変化させながら）
という流れで条件に合うパターンの等差数列を列挙する
方法が考えられます。
すこしサンプルを書いてみました。
コンソール入力しなければデフォルト値が入力され、
出力数列に最低限必要な個数を入力します。
問題にあわせた実行プログラムの例
C言語ソース "arith_seq.c" (BCC32でコンパイル)
#include "stdio.h" #include "string.h" #define AryNum(arr) (sizeof(arr)/sizeof(arr[0])) // 配列長を出すマクロ #define MAX_RANGE 32767 // 入力値の範囲(+-) #define BUFF_SIZE 100 // 出力数列表示用の文字列バッファサイズ #define IN_BUFF_SIZE 80 // 入力バッファサイズ #define START_EQ_DIFF 1 // 最初に調べる等差 #define INSEQ_SIZE 100 // 入力配列の要素数 // 関数プロトタイプ int getMax( int ary[], int num, int* pIdx); int getMin( int ary[], int num, int* pIdx); // グローバル変数領域 // // 入力数列(配列)に初期値を設定 int inseq[INSEQ_SIZE]; // コンソール入力しないときにデフォルトで使われる値 int default_inseq[] = { 0, 1, 3, 4, 8, 9, 10 ,12 ,14, 15}; int nIn ; // 入力有効数 // 変数 int inseq_min = 0; // 入力数列の項の中で最小のもの int inseq_max = 0; // 入力数列の項の中で最大のもの // int equal_diff = 1; // 等差（可変） int idxFirstTerm = 0; // 初項にする入力配列の添え字（可変） int valFirstTerm =0; // 初項値(可変) //////////////////////////////////////////// int main(void) { int i; // 添え字 int nInseq;// 入力配列の最大指標番号 int valMinTerm,valMaxTerm,idxMinTerm,idxMaxTerm;// 最小値・最大値と指標 int n; //等差数列のn int An; // 等差数列のn項目の値 int cntFind; // 同じ等差・初項で等差数列項に一致した個数 int cntTotalSeq=0 ; int need_term_num; // 最低必要項数 int valIn=0; // 同じ等差・初項のグループで、あるAnが入力配列内に見つかったかどうかの発見フラグ int flgFind; char buff[BUFF_SIZE]; // 出力数列用の文字バッファ char w_buff[20]; // 項値⇒文字変換用バッファ char in_buff[IN_BUFF_SIZE]; // 入力バッファ char des; int flgOutEqLabel; // 等差グループのラベルの出力フラグ printf("[等差数列抽出プログラム]\n"); strcpy(in_buff,""); printf("入力数列をコンソール入力しますか？(y/n):"); des = fgetc(stdin); if( des =='y' ){ // yes コンソール入力 fflush(stdin); i=-1; printf("項を入力（整数,1項ずつ/終了=Enterのみ)\n"); while ( i < INSEQ_SIZE ) { printf("%d項:",i+2); fgets(in_buff, IN_BUFF_SIZE, stdin); nIn = sscanf(in_buff, "%d", &valIn); if(nIn !=1) { if( i==-1){ printf("何も入力されていません\n"); }else{break;} }else{ i++; inseq[i] = valIn; } } // 配列の最大indexを格納 nInseq = i+1; }else{ // デフォルト値を代入 for (i = 0;i < AryNum(default_inseq) ;i++) { inseq[i] = default_inseq[i]; } // 配列の最大indexを格納 nInseq = AryNum(default_inseq); } fflush(stdin); // 入力配列の表示 printf(" 入力数列(配列):\n"); printf(" ={"); for(i=0; i< nInseq; i++){printf("%d ",inseq[i]);} printf("}\n"); printf(" (要素数 %d", nInseq); // 最大最小 valMaxTerm = getMax(inseq, nInseq, &idxMaxTerm); valMinTerm = getMin(inseq, nInseq, &idxMinTerm); printf(" 最小=%d(%d番目) , 最大 =%d(%d番目)\n", valMinTerm, idxMinTerm+1, valMaxTerm, idxMaxTerm+1); nIn = 0; while( nIn != 1) { // 入力 printf("(出力数列条件入力)\n 最低必要な連続項数を入力してください:"); fgets(in_buff, IN_BUFF_SIZE, stdin); nIn = sscanf(in_buff, "%d", &need_term_num); } printf(" --抽出結果--: \n"); // 抽出 // 等差の切り替え 1,2,... for( equal_diff = START_EQ_DIFF ; equal_diff < valMaxTerm; equal_diff++) { flgOutEqLabel = 1; // 初項の切り替え 1番目, 2番目, ... for(idxFirstTerm = 0; idxFirstTerm < nInseq ; idxFirstTerm++) { cntFind = 0; // 発見数クリア strcpy(buff, ""); // バッファクリア // 初項の値を取得 valFirstTerm = inseq[idxFirstTerm]; // nのループ for(n=1; n < valMaxTerm ; n++) { // 等差数列の項の式を計算 // 項 = 初項 + 等差 *(n-1) An = ( valFirstTerm + equal_diff *( n-1) ); // 等差数列の項の式に一致するものが、 // 入力配列の中の、初項以降の部分にあるかどうかを走査して検査 // 全く見つからなくなったら終了 flgFind =0; for( i= idxFirstTerm; i< nInseq; i++) { if( inseq[i] == An ) { strcpy(w_buff,""); // 見つかったら抜ける sprintf(w_buff, "%d " , inseq[i]); // 文字化 strcat(buff, w_buff ) ; // 文字連結 flgFind = 1; break; } } // 見つかったかどうか if( flgFind == 1){ cntFind++; } else{break; } } // 見つかった個数を判定 if( cntFind >= need_term_num) { // 画面出力 if( flgOutEqLabel == 1 ) { printf(" 等差=%d の数列グループ\n", equal_diff); flgOutEqLabel = 0; } printf(" 初項=%d, {An=%d+%d(n-1)}:" , valFirstTerm, valFirstTerm,equal_diff ); printf(" (%s)\n", buff); cntTotalSeq++; } } } printf(" \n 総抽出数列数= %d (数列)",cntTotalSeq); return (0); } //////////////////////////////////////////// // 最大値を求める int getMax( int ary[], int num, int* pIdx) { int myMax = -MAX_RANGE; int idxMax= 0,i; for( i = 0; i < num ; i++) { if( ary[i] > myMax ){myMax = ary[i];idxMax = i;} } *pIdx = idxMax; return (ary[idxMax]); } //////////////////////////////////////////// // 最小値求める int getMin( int ary[], int num, int* pIdx) { int myMin = MAX_RANGE; int idxMin=0,i; for( i = 0; i < num ; i++) { if( ary[i] < myMin ){myMin = ary[i];idxMin = i;} } *pIdx = idxMin; return (ary[idxMin]); }
