C言語について質問です。このプログラムの作成方法

質問

以下のプログラムは隣の数を引いた値が下に行き、すべての数字が重ならないようにするプログラムです。完成したのは良いですが、凄く見にくいプログラムになってしまいました。
見やすいように修正箇所を教えて頂けますか？
ttp://ideone.com/cJyaH

回答No.6

麻野 なぎ（@AsanoNagi） · ベストアンサー

では最後に何段でもいけるやつ。
ただ、本質的に効率無視のプログラムなので、５段（= 15まで）はちゃんと出たけど、６段（= 21まで）は該当無しという結果が出て、７段（= 28まで）に至っては、時間がかかりすぎて終わらなかった。
４段や３段はきっちり答が出た。

#include <stdio.h>
#include <stdlib.h>

#define maxStep (5)
#define numOfCell (maxStep * (maxStep + 1) / 2)

static int firstLine[maxStep];

static void init(void)
{
int i;
for(i = 0; i < maxStep; i++)
firstLine[i] = 0;
}

static int checkNum(int cell[])
{
int i;
int j;

for(i = 0; i < numOfCell; i++)
{
if (cell[i] < 1) return 0;
if (cell[i] > numOfCell) return 0;
}

for(i = 0; i < numOfCell - 1; i++)
for(j = i + 1; j < numOfCell; j++)
if (cell[i] == cell[j]) return 0;

return 1;
}

static void disp(int num[])
{
int i;
int j;
int dispPos = 0;

printf("\n\n");

for(i = 0; i < maxStep; i ++)
{
printf("%*s", i * 2, "");

for (j = 0; j < maxStep - i; j++)
printf("%4d", num[dispPos++]);

printf("\n");
}
}

static int getALine(int cell[])
{
int i;
firstLine[0]++;
for (i = 0; i < maxStep - 1; i++)
{
if (firstLine[i] > numOfCell)
{
firstLine[i] = 0;
firstLine[i + 1]++;
}
}
if (firstLine[maxStep - 1] > numOfCell) return 0;

for(i = 0; i < maxStep; i++)
cell[i] = firstLine[i] + 1;

return 1;
}

static void expand(int cell[])
{
int i;
int j;
int doneCount = maxStep;

for(i = maxStep - 1; i >= 1; i--)
{
int leftOfThisLine = doneCount;
int leftOfLastLine = doneCount - i - 1;

for (j = 0; j < i; j++)
cell[leftOfThisLine + j] = abs(cell[leftOfLastLine + j] - cell[leftOfLastLine + j + 1]);

doneCount += i;
}
}

int main()
{
int cell[numOfCell];

init();

while(getALine(cell))
{
expand(cell);
if (checkNum(cell)) disp(cell);
}

return 0;
}

回答No.5

麻野 なぎ（@AsanoNagi）

しまった……。
No.2 の回答ですが、そもそも、
int canSubtract(int a, int b, int c) // 引き算が成立するか？
なんて定義する必要ありませんでした。

if (canSubtract(i3, i2, i1))
は
if (abs(i3 - i2) == i1)
でOK

以下同じ。

回答No.4

麻野 なぎ（@AsanoNagi）

さて、先のプログラムで使った（重複を気にしないで）全部の数字を生成する方法は、実は、数字の位取りの方法と同じです。
ここでは、（同じ事なのですが）15進数を使用して、各桁の数字を使うという方法で少し直してみました。

また、いくつかループにしていなかった部分をループに直しています。

いずれにしても、このプログラムは「効率は悪い」です。
こういうソースでも答えが出てしまう時代でもありますが。

もう少し複雑な場合では、既に回答があるように、バックトラックなど使用して、効率を稼ぐ必要があります。

なお、バックトラックというのは、見かけは、「再帰呼び出しを使ってループを見えなくする方法」でもあります（そういうものではないですけど）

その意味では、オリジナルのプログラムが、バックトラックへは近道かと思います。

#include <stdio.h>
#include <stdlib.h>

#define maxNum 15

int isOK(int num[])
{
int i;
int forCheck[maxNum] = {0};

for(i = 0; i < maxNum; i++)
{
if (num[i] < 0) return 0; // 小さすぎる
if (num[i] > maxNum) return 0; // 大きすぎる
if (forCheck[num[i] - 1] != 0) return 0; // 重複
forCheck[num[i] - 1] = 1; // 重複チェック用
}
return 1;
}

void disp(int num[])
{
int i;
int j;
int startPos[] = { 0, 5, 9, 12, 14};
int endPos[] = { 4, 8, 11, 13, 14};

printf("\n\n");

for(j = 0; j < 5; j ++)
{
printf("%*s", j * 2, "");

for(i = startPos[j]; i <= endPos[j]; i++)
printf("%4d", num[i]);
printf("\n");
}
}

int main()
{
int num[maxNum];
int i;
int j;

int base;
int ketaWk;

int startPos[] = { 5, 9, 12, 14};
int endPos[] = { 8, 11, 13, 14};
int diff[] = { 5, 4, 3, 2};

for(base = 0; base < 15 * 15 * 15 * 15 * 15; base++)
{
// 答えは先頭の5つの数字で決まる。
// だから基本になる数字を 00000(15) から EEEEE(15) まで変化させて
// 各桁を数値として使用する
//

ketaWk = base;
for(i = 0; i <= 4; i++)
{
num[i] = (ketaWk % 15) + 1;
ketaWk /= 15;
}

// ２段目以降の計算
for(j = 0; j <= 3; j++)
{
for(i = startPos[j]; i <= endPos[j]; i++)
num[i] = abs(num[i - diff[j] + 1] - num[i - diff[j]]);
}
// 結果を確認
if (isOK(num)) disp(num);
}

return 0;
}

回答No.3

麻野 なぎ（@AsanoNagi）

オリジナルとは考え方を変えて、

・数字の組み合わせを全部出してみる（この段階では重複を気にしない）
・ただし、答えは先頭の段（５つの数字）だけで決まるので、５個しか考えない
・２段目以降の計算をしてみる
・最後に妥当性をチェックする

という考え方で書いたのがこのソースです。

#define maxNum 15

int isOK(int num[])
{
int i;

int forCheck[maxNum] = {0};

for(i = 0; i < maxNum; i++)
{
if (num[i] < 0) return 0; // 小さすぎる
if (num[i] > maxNum) return 0; // 大きすぎる
if (forCheck[num[i] - 1] != 0) return 0; // 重複
forCheck[num[i] - 1] = 1; // 重複チェック用
}
return 1;
}

void disp(int num[])
{
int i;

printf("\n\n");

for(i = 0; i <= 4; i++)
printf("%4d", num[i]);
printf("\n");

printf(" ");
for(i = 5; i <= 8; i++)
printf("%4d", num[i]);
printf("\n");

printf(" ");
for(i = 9; i <= 11; i++)
printf("%4d", num[i]);
printf("\n");

printf(" ");
for(i = 12; i <= 13; i++)
printf("%4d", num[i]);
printf("\n");

printf(" ");
for(i = 14; i <= 14; i++)
printf("%4d", num[i]);
printf("\n");
}

int main()
{
int num[maxNum];
int i;

for(i = 0; i < 5; i++)
num[i] = 1;

while(1)
{
num[0]++;
for(i = 0; i < 4; i++)
{
if (num[i] > maxNum) // この桁があふれた
{
num[i] = 1;
num[i + 1]++;
}
}
if (num[4] > maxNum) break; // すべての場合を尽くした。

// ２段目以降の計算
for(i = 5; i <= 8; i++)
num[i] = abs(num[i - 4] - num[i - 5]);

for(i = 9; i <= 11; i++)
num[i] = abs(num[i - 3] - num[i - 4]);

num[12] = abs(num[10] - num[9]);
num[13] = abs(num[11] - num[10]);
num[14] = abs(num[13] - num[12]);

if (isOK(num)) disp(num);
}

return 0;
}

回答No.2

麻野 なぎ（@AsanoNagi）

まずは、構造を保持して直してみました。
いかんせん、ネストしたループはプログラミングの大敵ですし、
また、あれをやりながらこれをやるという（数字の範囲をチェックしながら、引き算の結果になるかどうかチェックして、重複チェックをする）というのは、混乱の元です。

ここでは、その構造は保持したまま、引き算の結果になるような数字を使うのではなく、全部の数字を 1 から 15まで変化させて、引き算の結果になるかどうかを確認するようにしています。

こうすると、数値は必ず 1 から 15に収まるので、範囲チェックも不要です。
また、重複チェックは最後にまとめてやっています。

オリジナルのものに比較すると、「効率」という点では明らかに劣りますが。

#include <stdio.h>

int canSubtract(int a, int b, int c) // 引き算が成立するか？
{ // a - b == c or b - a == c のとき、1 を返す
if (a - b == c) return 1;
if (b - a == c) return 1;
return 0;
}

// こうすると、たとえば、for (i5 = i4 - i2; i5 <= i4 + i2; i5 += 2 * i2)
// という謎の式は
// for (i5 = 1; i5 <= 15; i++)
// { if canSubtract(i5, i4, i2) で置き換えできる。

int checkDup(int use[], int num) // 重複チェック
{
if (use[num]) return 1;
use[num] = 1;
return 0;
}

int main(void)
{
int i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11, i12, i13, i14, i15;

for (i1 = 1; i1 <= 15; ++i1) {
for (i2 = 1; i2 <= 15; ++i2) {
for (i3 = 1; i3 <= 15; i3++) {
if (canSubtract(i3, i2, i1)) {
for (i4 = 1; i4 <= 15; ++i4) {
for (i5 = 1; i5 <= 15; i5++) {
if (canSubtract(i5, i4, i2)) {
for (i6 = 1; i6 <= 15; i6++) {
if (canSubtract(i6, i5, i3)) {
for (i7 = 1; i7 <= 15; ++i7) {
for (i8 = 1; i8 <= 15; i8++) {
if (canSubtract(i8, i7, i4)) {
for (i9 = 1; i9 <= 15; i9++) {
if (canSubtract(i9, i8, i5)) {
for (i10 = 1; i10 <= 15; i10++) {
if (canSubtract(i10, i9, i6)) {
for (i11 = 1; i11 <= 15; ++i11) {
for (i12 = 1; i12 <= 15; i12++) {
if (canSubtract(i12, i11, i7)) {
for (i13 = 1; i13 <= 15; i13++) {
if (canSubtract(i13, i12, i8)) {
for (i14 = 1; i14 <= 15; i14++) {
if (canSubtract(i14, i13, i9)) {
for (i15 = 1; i15 <= 15; i15++) {
if (canSubtract(i15, i14, i10))
{
int use[16] = {0};
int result = 0;

result += checkDup(use, i1);
result += checkDup(use, i2);
result += checkDup(use, i3);
result += checkDup(use, i4);
result += checkDup(use, i5);

result += checkDup(use, i6);
result += checkDup(use, i7);
result += checkDup(use, i8);
result += checkDup(use, i9);
result += checkDup(use, i10);

result += checkDup(use, i11);
result += checkDup(use, i12);
result += checkDup(use, i13);
result += checkDup(use, i14);
result += checkDup(use, i15);

if (! result)
printf("%2d %2d %2d %2d %2d\n %2d %2d %2d %2d\n %2d %2d %2d\n %2d %2d\n %2d\n\n", i15, i14, i13, i12, i11, i10, i9, i8, i7, i6, i5, i4, i3, i2, i1);

}

}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
return 0;
}

回答No.1

asuncion

関連する質問でいいかげんな答えをしてしまった私が言うのもアレですが、
総当たり法の定番ともいえる「バックトラック」について調べてみるといいかもしれません。
再帰呼び出しを使うので、取っつきにくいところがあるかもしれません。