Memorandums?

This blog is written about technical-discovery and daily-event.

最小公倍数1


C言語で可変長の数を入力させ、その最小公倍数を求めるプログラムを作りました。

最小公倍数(LCM = Least Common Multiple)プログラムは以下の通りです。


かなり冗長だと思いますが、とりあえずはこれで実行はできます...

標準リファレンスの関数はできるだけ使わないようにしました。


動的配列を扱うためにmalloc関数を使用。
ポインタ変数に引数にサイズを指定したmalloc関数の戻り値を代入。
for文でいろいろと回して、入力した数を代入。
LCMを実装するための関数は二つ。

int getEqualValue(int* num, int item)

関数によって、配列の要素が全て同じ値になっているかをチェック

int getMinValue(int* num, int item)

関数によって、最も小さい値の配列要素番号を返す

  1. getEqualValue()で3つの値が等しいかチェック
  2. getMinValue()で最小値をgetし、最小値に初項2,公差1のカウントアップ変数を掛ける
  3. ループによって繰り返す


例えば、1,2,3の3つの数が入力されたとき、

  1. 1,2,3は等しくない
  2. 最小値は1
  3. 最小値に2を掛ける
  4. 2,2,3となり、まだ全ての値は等しくない
  5. 最小値は2
  6. 最小値の元の数1を3倍する
  7. 3,2,3となり、等しくない
  8. 3,4,3→4,4,3→4,4,6→5,4,6→5,6,6→6,6,6
  9. 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;
}
Remove all ads