最小公倍数1
C言語で可変長の数を入力させ、その最小公倍数を求めるプログラムを作りました。
最小公倍数(LCM = Least Common Multiple)プログラムは以下の通りです。
かなり冗長だと思いますが、とりあえずはこれで実行はできます...
標準リファレンスの関数はできるだけ使わないようにしました。
動的配列を扱うためにmalloc関数を使用。
ポインタ変数に引数にサイズを指定したmalloc関数の戻り値を代入。
for文でいろいろと回して、入力した数を代入。
LCMを実装するための関数は二つ。
int getEqualValue(int* num, int item)
関数によって、配列の要素が全て同じ値になっているかをチェック
int getMinValue(int* num, int item)
関数によって、最も小さい値の配列要素番号を返す
- getEqualValue()で3つの値が等しいかチェック
- getMinValue()で最小値をgetし、最小値に初項2,公差1のカウントアップ変数を掛ける
- ループによって繰り返す
例えば、1,2,3の3つの数が入力されたとき、
- 1,2,3は等しくない
- 最小値は1
- 最小値に2を掛ける
- 2,2,3となり、まだ全ての値は等しくない
- 最小値は2
- 最小値の元の数1を3倍する
- 3,2,3となり、等しくない
- 3,4,3→4,4,3→4,4,6→5,4,6→5,6,6→6,6,6
- LCM = 6
2,2,3になった時点で、2と3のLCMを求めるようにすれば、
1,2,3→2,2,3=2,3→4,3→4,6→6,6
となり、手順を減らせそうです。
また、コードも再帰などを使えば、無駄が減らせそう。
#include<stdio.h> #include<stdlib.h> int main() { int i, item; printf("Index: "); scanf("%d", &item); int* num; num = (int *)malloc(sizeof(int) * item); int* cnt; cnt = (int *)malloc(sizeof(int) * item); for(i = 0; i < item; i++) cnt[i] = 2; int* reserve_num; reserve_num = (int *)malloc(sizeof(int) * item); if(num == NULL || reserve_num == NULL || cnt == NULL) exit(0); int minIndex; for(i = 0; i < item; i++) scanf("%d", &num[i]); for(i = 0; i < item; i++) reserve_num[i] = num[i]; while(!getEqualValue(&num[0], item)) { minIndex = getMinValue(&num[0], item); num[minIndex] = reserve_num[minIndex] * cnt[minIndex]; cnt[minIndex]++; } printf("L.C.M = %d\n", num[0]); free(num); free(reserve_num); free(cnt); return 0; } int getMinValue(int* num, int item) { int min = num[0]; int i; int j = 0; for(i = 1; i < item; i++) { if(min > num[i]) { min = num[i]; j = i; } } return j; } int getEqualValue(int* num, int item) { int judge = 1; int i; for(i = 1; i < item; i++) { if(num[i-1] != num[i]) judge = 0; } return judge; }