配列を扱ったc言語が変な出力で出てきて、原因がわかりません ※読みやすいようコメント多めです

Question

やりたいこと

1を何かで割ったときの循環節の長さを調べてます。
(ex)1÷7=0.14285714285714285...で、長さが六の142857が繰り返されるので循環節は６です。
また、便宜上割り切れる場合と循環小数にならない場合は循環節は０としてます。
pythonで作りましたが、わる数を増やしていった時に速度が足らず、対応出来なかったので高速で動くc言語で書き換えようとしました
pythonでは問題なく動作しましたがCでおかしな挙動を見せました。アルゴリズムはほぼ同じなので自分の知識不足により変な結果になっているものと思われます。
pythonも大概ですが、Cはかなりの初心者なのでお手柔らかにお願いします

##入出力
入力はinput()やscanf()などを介すことなくend_numという変数に直接入力する形をとってます
出力はpythonでは配列、cでは配列をそのまま出力できないのでpythonの配列っぽく出力させてます

わかりづらいことは実際のコードをみていただければわかると思います
##pythonでのコード

import numpy as np
count = 0　 #　今何回割り算したかを記録します
end_num = 100　 # 入力です。わる数の上限です。自分の環境では100000から速度不足が深刻で計算できませんでした。
num_list = list(np.zeros(end_num, dtype=int))　 # 余りを記録するリスト。同じ余りが出てきたときが循環が一区切りついたときなので(実際に筆算をするとわかりやすいです)
output_list = list(np.zeros(end_num+1, dtype=int))  # 出力用のリストです。


for i in range(2, end_num + 1):
    if i % 2 == 0 or i % 5 == 0:
        output_list[i] = 0  # 2や5の倍数でわると必ず循環しないので0を出力のリストに入れます
    else:
        left = 1 % i # 余りです
        while True: # 同じ余りが出るまでループを続けます
            if left in num_list:
                output_list[i] = count - num_list.index(left)  
　　　　　　　　　　# 割り算した回数-今出た余りは過去に何回目で出たかで循環節が求まります。実際に筆算するとわかりやすいです
                break
            else:
                num_list[count] = left
                left *= 10
                left %= i  # でた余りを十倍してもとの数で再度割る。実際の筆算の操作と同じです
                count += 1

        count = 0  # 循環節が求まったので次の数に進むために再度初期化しておきます
        num_list = list(np.zeros(end_num, dtype=int))

print(output_list)

出力
[0, 0, 0, 1, 0, 0, 0, 6, 0, 1, 0, 2, 0, 6, 0, 0, 0, 16, 0, 18, 0, 6, 0, 22, 0, 0, 0, 3, 0, 28, 0, 15, 0, 2, 0, 0, 0, 3, 0, 6, 0, 5, 0, 21, 0, 0, 0, 46, 0, 42, 0, 16, 0, 13, 0, 0, 0, 18, 0, 58, 0, 60, 0, 6, 0, 0, 0, 33, 0, 22, 0, 35, 0, 8, 0, 0, 0, 6, 0, 13, 0, 9, 0, 41, 0, 0, 0, 28, 0, 44, 0, 6, 0, 15, 0, 0, 0, 96, 0, 2, 0]

いくつかの数を調べてみた所実際の計算結果と一致したのでおそらく欠陥はないです。

##Cでのコード

#include <stdio.h>

int existinArray(int array[], int size, int element); 
/*
 要素が存在するかを判定
 引数：
 	int array[] 調べたい配列
	int size 調べたい配列の要素数
	int element 要素
戻り値:
	int 0か1。実質Bool型
*/
int indexArray(int array[], int size, int element);
/*
 要素がどこに存在するかを判定
 引数：
 	int array[] 調べたい配列
	int size 調べたい配列の要素数
	int element 要素
戻り値:
	int 要素のインデックスを表示
*/

int main(void){
	size_t count = 0; //今何回割り算したかを記録します
	int end_num = 100; //入力です。割る数の上限です。
	int numArray[end_num];　//余りを記録する配列。同じ余りが出てきたときが循環が一区切りついたときなので(実際に筆算をするとわかりやすいです)
	for (int i = 0; i < end_num; i++){
		numArray[i] = 0;
	}
	int outputArray[end_num+1];  //出力用の配列です。
	for (int i = 0; i < end_num+1; i++){
		outputArray[i] = 0;
	}
	int left; //余りです

	for (int i = 2; i < end_num + 1; i++){
		if (i % 2 == 0 || i % 5 == 0){
			outputArray[i] = 0; // 2や5の倍数でわると必ず循環しないので0を出力の配列に入れます
		}else{
			left = 1 % i; // 余りです
			while (1){　// 同じ余りが出るまでループを続けます
				if (existinArray(numArray, end_num, left) == 1){ //余りが過去にでた余りと一致するかを判定
					outputArray[i] = count - indexArray(numArray, end_num+1, left);
　　　　　　　　　　　// 割り算した回数-今出た余りは過去に何回目で出たかで循環節が求まります。実際に筆算するとわかりやすいです
					break;
				}else{
					numArray[count] = left;
					left *= 10;
					left %= i;// でた余りを十倍してもとの数で再度割る。実際の筆算の操作と同じです
					count ++;
				}
			}
		count = 0;
		}
	}

	// 出力部
	printf("[");
	for (int i = 0; i < (sizeof(outputArray)/sizeof(outputArray[0])); i++){
		printf("%d,", outputArray[i]);
	}
	printf("]");
}

int existinArray(int array[], int size, int element){
	size_t output = 0;
	for (int i = 0; i < size; i++){
		if (array[i] == element){
			output = 1;
			break;
		}
	}
	return output;
}

int indexArray(int array[], int size, int element){
	size_t output = 0;
	for (int i = 0; i < size; i++){
		if (array[i] == element){
			break;
		}else{
			output ++;
		}
	}
	return output;
}

出力
[0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,]
※最後のコンマは特に気にしなくて大丈夫です。

Ubuntu 20.04.1 LTS x86_64のターミナルでgccコマンド打ってコンパイルしてます。

Comments

[tiitoi]

以下は インデックス=end_num にアクセスしてるので out of range になりませんか？

int numArray[end_num];
for (int i = 0; i < end_num + 1; i++)

[renge]

本当ですね！もともと初期化せずに使ってて、質問を書き込んでる途中に変更したので気づきませんでした。ただ、上記のように書き直して再度コンパイルして走らせてもうまく行かなかったです...

[Soei]

質問内容から外れますが、pythonの方もおかしくありませんか?
『2や5の倍数でわると必ず循環しないので0を出力の配列に入れます』とありますが、6は2の倍数で、1 / 6 = 0.16666... は循環します。

[renge]

本当ですね。素因数が2と5のみっていうのが条件なので余りだけで判定するのは無理がありそうですね。素直に素因数分解します。

Answer 1

existinArrayでチェックする範囲が間違ってませんか。

-if (existinArray(numArray, end_num, left) == 1) { //余りが過去にでた余りと一致するかを判定
+if (existinArray(numArray, count, left) == 1) { //余りが過去にでた余りと一致するかを判定

Answer 2

num_list = list(np.zeros(end_num, dtype=int)) に該当する処理が C 言語のほうにはないです。memset() で numArray を初期化してください。

ループ内の count = 0; の上に追加

+ memset(numArray, 0, sizeof(numArray));

追記

修正依頼欄で他のSoeiさんが指定してくださってますが、i % 2 == 0 or i % 5 == 0 で循環節の長さ0とするのはおかしいですね。
反例: 1/12 = 0.08333333333
反例: 1/90 = 0.01111111111

#include <stdio.h>
#include <string.h>

#define N 100

/**
 * @brief 値 value が配列 array に見つかった場合はそのインデックス、見つからなかった場合は -1 を返す。
 * @param[in] array 配列
 * @param[in] size 配列のサイズ
 * @param[in] value 検索する値
 * @return インデックス
 */
int find_index(const int array[], int size, int value)
{
    int i = 0;
    while (i < size && array[i] != value)
        ++i;

    return i == size ? -1 : i;
}

/**
 * @brief 1 / value の循環節の長さを返す。
 * @param value 値
 * @return 循環節の長さ
 */
int func(int value)
{
    int array[N] = {0};
    int mod = 1;
    int i, j;

    for (i = 0; i < N; ++i) {
        mod %= value;
        if (mod == 0)
            return 0; // 割り切れた場合、循環節の長さは0

        j = find_index(array, i, mod);
        if (j != -1)
            return i - j; // 過去に同じ余りがあった場合は j, j + 1, ..., i - 1 までが循環節

        array[i] = mod;
        mod *= 10;
    }
}

int main()
{
    // 1 ~ N の循環節の長さを出力する。
    for (int i = 1; i <= N; i++)
        printf("%d: %d\n", i, func(i));
}

Comments

[SHOMI]

C++は{}で通りますが、C言語では{0}としないとエラーですよ。

[tiitoi]

コメントありがとうございます。
そうなのですね。C++ でコンパイルしてました。

[renge]

初期化の部分が足りていませんでしたね！ベストアンサー本当に迷いましたがSHOMIさんにさせていただきました。今思えばSHOMIさんの方法で問題なく動作しますけど保守性の観点から言うと初期化したほうが良さそうですね。申し訳ないです。
プログラムの方もより簡潔なコードをかいていだだけて、非常に参考になります。
コードがうまく読めなくて質問なのですが、
例えばi = 2のときってmodの値が1になると思いますけど、これはどういう流れで0になってますか？

[tiitoi]

mod %= 2 (mod: 1)
mod *= 10 (mod: 10)
mod %= 2 (mod: 0)

2回目のループで0になります。

[renge]

本当に申し訳ないんですけど、質問いいですか？
ループを便宜上0回目からカウントするとおっしゃる通り1回目でmodが0になり、2回目でfind_indexで検出されて、jには1が格納されますよね？それで、funcは2-1で1を返すと思ったのですが、実際コードを回すと0が出力されてます。望んだ結果ではあるのですが、なぜこうなるのか教えて頂きたいです。
何度もお聞きしてしまい本当に申し訳ないです。

[tiitoi]

value がいくつのときの 1 / value の話をしていますか？
value = 2 のときの話であれば、
0. mod (変数の中身 mod: 0)
1. mod %= 2 (1 を 2 で割ると余り1なので、変数の中身 mod: 1)
2. mod *= 10 (変数の中身 mod: 10)
3. mod %= 2 (10 を 2 で割ると余り0なので、変数の中身 mod: 0)
4. if(mod == 0) return 0; で関数は0を返して終了する

という処理です。割り切れた時点でその先の find_index() に到達する前に return 0 で終了します。

[tiitoi]

念のため確認ですが、return した時点で値を返して関数が終了するというのは大丈夫でしょうか？

[renge]

あ、本当ですね。毎回割り切れたかどうかを判定してるんですか！自分には全くなかった発想で、コードが書いてあるにもかかわらず読み飛ばしてしまいました...本っ当に参考になりました。ご親切に何度も回答くださり本当にありがとうございました