どうプログラムを書けば良いか分からなくなったので質問させてください.

不等間隔のデータの中から,等間隔な部分を抜き出す方法?
例えば,「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」,「8 12 14」,「9 12 15」がありますが,これをCとかFortranとかで書くとどう書けば良いのでしょう?具体的なソースを教えて頂けたらと思います.また,決まったやり方があるのでしたら教えて下さい.

回答の条件
  • 1人2回まで
  • 登録:2007/06/06 01:05:07
  • 終了:2007/06/08 18:13:57

ベストアンサー

id:jack_sonic No.6

じゃっくそにっく回答回数123ベストアンサー獲得回数252007/06/06 22:54:58

ポイント60pt

こんにちは。最適化問題は別として、

比較的理論的にとらえやすいアルゴリズムで説明してみます。

[アルゴリズムについて]

質問文での、「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) )の等差数列

等差数列を、(最適化は別として)理論上わかりやすく抜き出す方法の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を変化させながら)

という流れで条件に合うパターンの等差数列を列挙する

方法が考えられます。


すこしサンプルを書いてみました。

コンソール入力しなければデフォルト値が入力され、

出力数列に最低限必要な個数を入力します。

問題にあわせた実行プログラムの例

[f:id:jack_sonic:20070606222652j:image]

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]);
}
id:taki

考え方まで詳しく説明して頂きありがとうございます.数列という単語を久々に聞いて,もやもやがちょっと晴れました!

2007/06/07 09:47:36

その他の回答(5件)

id:Z9M9Z No.1

Z9M9Z回答回数343ベストアンサー獲得回数112007/06/06 01:36:54

ポイント10pt
0 1 3 4 8 9 10 12 14 15
+ 1 3 4 8 9 10 12 14 15
- + 2 3 7 8 9 11 13 14
- - + 1 5 6 7 9 11 12
- - - + 4 5 6 8 10 11
- - - - + 1 2 4 6 7
- - - - - + 1 3 5 6
- - - - - - + 2 4 5
- - - - - - - + 2 3
- - - - - - - - + 1

このように全差分をつくって配列にでもおいて、0から順に、同じ差分で2つ以上たどっていけるかをチェックするのはどうでしょう。0から4ずつをたどる例を赤く、1から7ずつをたどる例を青くしてみました。ソースじゃなくてすんませんが。

n個のデータならnの2乗の手間で終わりそう。

例の8 12 14は10 12 14ですね。

id:taki

ソースを見てみたいです.

2007/06/06 10:16:38
id:a3hys No.2

a3hys回答回数11ベストアンサー獲得回数12007/06/06 07:40:27

ポイント20pt

先頭から順に、間隔を0から順に、2回(3個目に)辿れるかをチェック、とそれぞれループで行う単純なものですが叩き台に・・・。

#include <stdio.h>
void check(int*);
void foo(void);

int dat[16] = { 1,1,0,1,1,0,0,0,1,1,1,0,1,0,1,1 };

void foo(void)
{
	int dif; //ループ用(間隔)
	int bgn; //ループ用(開始位置)
	int cnt; //等間隔のカウント
	int i;
	int tmp[16];

	// 探索開始位置
	for (bgn = 0; bgn < 16-2; bgn++) {
		// 等間隔の値
		for (dif = 1; dif < 16/2; dif++) {
			// 計算領域のクリア
			for (i=0; i < 16; ++i)
				tmp[i] = 0;
			cnt = 0;
			
			/////等間隔の存在チェック/////
			if (bgn-dif >= 0 &amp;&amp; dat[(bgn-dif)])
				continue; //探索済み除外
			//探索
			i = bgn;
			while (1) {
				if(i < 16 &amp;&amp; dat[i]) {
					tmp[i] = 1;
					i += dif;
					cnt++;
				} else {
					break;
				}
			}
			if (cnt>=3) {
				// 3個以上の等間隔部分があった場合
				check(tmp);
			}
		}
	}
}

void check(int *tmp) //確認用表示
{
	int i;
	printf("{ ");
	for (i=0; i<16; ++i) {
		if (tmp[i]) {
			printf("%d ", i);
		}
	}
	printf("}\n");
}

int main()
{
	foo();
	
	return 0;
}

※行数削減のため、勝手にデータを展開していたり、即値を使ったりしています。

id:taki

良い感じです.ありがとうございます.

2007/06/06 10:17:50
id:siigimaru No.3

siigimaru回答回数556ベストアンサー獲得回数52007/06/06 09:37:29

ポイント1pt

http://always-pg.com/c/runtime_rd/string/strtok.html

http://sometime.minidns.net/~ccgi/autostring.html


C言語ですが、文字分割的なソースを載せます。

id:taki

文字分割をどう使うのですか???

2007/06/06 10:18:51
id:Mook No.4

Mook回答回数1312ベストアンサー獲得回数3912007/06/06 12:42:53

ポイント60pt

>また,決まったやり方があるのでしたら教えて下さい.

プログラムでの「やり方」がアルゴリズムといわれるもので、アルゴリズムしだいで、プログラムの効率が大きく変わります。


初心者はプログラミングとはコードを書くことと思いがちですが、実際はこのアルゴリズムを設計することのほうが重要です。


a3hys さんのコードと似ていますが、データの扱い方が異なっていますので、その違いを見比べてみると面白いかと思います。

ほとんどCでも動くと思いますが、一部 C++ の文法を使用しているので、拡張子をcpp にして実行してください。

(変数の宣言とコメントを修正すれば、C でも動作します。)

#include <stdio.h>

static	void	checkSequence(  int arCnt, int *arNum );
static int checkNum( int sNum, int *arNum, int cnt );
static void printSequence( int *seqList, int *numCnt );

//------------------------------------------------------
void main( void ) {
//------------------------------------------------------
    int arNum[] = {0, 1, 3, 4, 8, 9, 10, 12, 14, 15 }; // 検索データ : 昇順に定義すること
    checkSequence( sizeof( arNum ) / sizeof(int), arNum );
}

//------------------------------------------------------
static	void	checkSequence(  int arCnt, int *arNum ) {
//------------------------------------------------------
    int existNum = 0;
    int nextNum;
    int seqList[10];
  
    for( int eqDiff = 1 ; eqDiff<=arNum[arCnt-3] ; eqDiff++ ) { // 等差でループ
        for( int firstNum=0 ; firstNum<eqDiff ; firstNum++ ) {  // 初項でループ
            for( nextNum = firstNum ; nextNum<=arNum[arCnt-1] ; nextNum+=eqDiff ) {
                if( checkNum( nextNum, arNum, arCnt ) == 1 )
                    seqList[existNum++] = nextNum;
                else
                    printSequence( seqList, &existNum );
            }
            printSequence( seqList, &existNum );
        }
    }
    return;
}
//------------------------------------------------------
static int checkNum( int sNum, int *arNum, int cnt ) { // データがあるかをチェック
//------------------------------------------------------
    int i;
    for ( i=0 ; i<cnt ; i++ ) {
        if ( arNum[i] == sNum ) return 1;
    }
    return 0;
}

//------------------------------------------------------
static void printSequence( int *seqList, int *numCnt ) { // データを表示
//------------------------------------------------------
    int i;
    if ( *numCnt >= 3 ) {
        printf("{ ");
        for( i=0 ; i<*numCnt ; i++ ) printf( "%d ", seqList[i] );
        puts("}");
    }
    *numCnt = 0;
}
id:taki

ありがとうございます.

勉強になります.

2007/06/06 15:19:07
id:aside No.5

aside回答回数339ベストアンサー獲得回数312007/06/06 15:05:56

ポイント60pt

あえてjavascript

<html>
<head>
<script language="javascript">
<!--
function calc() {
  // 結果格納用
  var sTemp = "";
  var sResult = "";
  // スペース区切りの値を配列へ変換
  var arrVal = document.getElementById("target").value.split(" ");
  // 配列内の文字列を数値へ変換
  var arrNum = new Array();
  for (var idx=0; idx < arrVal.length; idx++) {
    arrNum[idx] = parseInt(arrVal[idx], 10);
  }
  for (var idx = 0; idx < arrNum.length - 2; idx++) {
    for (var idx0=idx+1; idx0 < arrNum.length - 2; idx0++) {
      // 出力結果初期化
      sTemp = "";
      // 等間隔チェック用の間隔の値
      var iDeff = arrNum[idx0] - arrNum[idx];
      // 比較用値保存
      var iReff = arrNum[idx0];
      // チェック用フラグ
      var flg = false;
      for (var idx1=idx0+1; idx1 < arrNum.length; idx1++) {
        if ((arrNum[idx1] - iReff) == iDeff) {
          // 書き出し一回目は余分に出力する
          if (!flg) {
            flg = true;
            sTemp += arrNum[idx] + " " + arrNum[idx0];
          }
          // 値出力
          sTemp += " " + arrNum[idx1];
          // 比較用値設定
          iReff = arrNum[idx1];
        }
      }
      // 結果出力
      if (flg) {
        if (sResult.indexOf(sTemp) == -1) {
          sResult += sTemp + String.fromCharCode(13);
        }
      }
    }
  }
  document.getElementById("answer").innerText = sResult;
}
//-->
</script>.
</head>
<body>
<input type="text" id="target" style="width:100%;" value="0 1 3 4 8 9 10 12 14 15">
<input type="button" value="計算" onclick="calc()">
<br>
<textarea id="answer" style="width:100%;height:100%;"></textarea>
</body>
</html>
id:taki

あえての参戦ありがとうございます.

簡単に書けるもんですね.

2007/06/06 15:20:57
id:jack_sonic No.6

じゃっくそにっく回答回数123ベストアンサー獲得回数252007/06/06 22:54:58ここでベストアンサー

ポイント60pt

こんにちは。最適化問題は別として、

比較的理論的にとらえやすいアルゴリズムで説明してみます。

[アルゴリズムについて]

質問文での、「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) )の等差数列

等差数列を、(最適化は別として)理論上わかりやすく抜き出す方法の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を変化させながら)

という流れで条件に合うパターンの等差数列を列挙する

方法が考えられます。


すこしサンプルを書いてみました。

コンソール入力しなければデフォルト値が入力され、

出力数列に最低限必要な個数を入力します。

問題にあわせた実行プログラムの例

[f:id:jack_sonic:20070606222652j:image]

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]);
}
id:taki

考え方まで詳しく説明して頂きありがとうございます.数列という単語を久々に聞いて,もやもやがちょっと晴れました!

2007/06/07 09:47:36
  • id:studioes
    C or Fortran限定?
  • id:taki
    他の言語でもアルゴリズムが分かるなら何でも結構です.
    よろしくお願いします.
  • id:taki
    fortranのソースも出来ればお願いします!
  • id:Mook
    明確にはアルゴリズムの説明をしていませんが a3hysさんの回答も、aside さんの回答も私のものも、基本は等差数列を検索するものです。ただ、その中で初項や等差をどのように扱うかが異なってきます。

    jack_sonic さんの回答は毎回丁寧ですね。頭が下がります。
    ただ、今回の解では 0,4,8,12 の中に含まれる 4,8,12 が別のグループとして、表示されてしまいますね。
    (他の方のは一応最長解を表示するようになってました)

    内部の実装とは別に、aside さんの方法はインパクトがありました。JavaScript では簡単に I/F が作成できる点もいいですね。C では 入力や配列の処理も一苦労ですが、これらが手軽に処理できるのも大きいです。
  • id:jack_sonic
    >Mook様
    大変ありがとうございます。
    そのとおりで、私の回答の仕様の場合は、
    等差数列を検出する際に、
    等差dが同じ数列グループでも、初項A1が違うもの、
    つまり、出力数列に対応する数学的な数列式{An=A1+d(n-1)}が
    異なる数列の場合に
    例{0,4,8,12}⇒{An=0+4(n-1)}
     {4,8,12}⇒{An=4+4(n-1)}
    別の数列として認識するようになっておりますので、
    皆さんが選ばれている最長解を選ぶ仕様のように、
    ”等差が同じ数列では、項数が最長の数列だけ選ぶ”
    というようにするには、
    "等差のグループごとに、検出したAn数列の最大項数を記録しておき、最も大きい項数を記録した数列のみ表示する"、
    という処理を追加する必要があるかと思います。


    >はてなの不具合についての報告
    はてなのスーパーpre記法の不具合についてなのですが、
    今回、a3hys様のご回答のソースの中で、C言語の比較演算子として
    入力されたと思われる「&&」記号が、
    はてなの回答システムによって勝手に
    「&amp;&amp;」に変換されてしまっているところなのですが、
    ご存知の方も多いと思うのですが、人力のスーパーpre記法の誤変換で、「&」がブラウザ表示で「&amp;(HTMLで&amp;amp」になる
    不具合があります。
    少し前からはてなアイデアで修正依頼を出しているのですが、
    http://i.hatena.ne.jp/idea/15391
    検証と修正に時間がかかるとのことです。
  • id:jack_sonic
    あ、すみません。コメントの一部間違い訂正です。
    下から8行目 C言語のx比較演算子ではなくて○論理演算子 です。
    失礼しました。
  • id:taki
    皆様ありがとうございました.
    みなさんのソースを参考に自分でも書いてみました.
    助かりました.

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません