三次元ヤング図形 数え上げ

[syakajin]

プログラミングについて質問です。

あるn(=1〜40)に対して

Σa[j] (任意のa[j]の足しあわせ)=n
a[j]≧1
a[j]>a[j+1]
a[j]>a[i+1][j]
iの最大値が偶数


をみたすa[j]の組が何個あるかを出すプログラムを作りたいのですが、力をお借りできないでしょうか。
できたらiが奇数の場合もお願いします。

[みけCAT]

使用する言語の指定や、途中まで書いたコードはありますか？

フォーラムルールより転載

どう質問していいか解らない時は、以下のテンプレをコピペして、

各項目に対して答える形で記載して下さい。

[hr]
[1] 質問文
　[1.1] 自分が今行いたい事は何か
　[1.2] どのように取り組んだか(プログラムコードがある場合記載)
　[1.3] どのようなエラーやトラブルで困っているか(エラーメッセージが解る場合は記載)
　[1.4] 今何がわからないのか、知りたいのか

[2] 環境 　
　[2.1] OS ： Windows, Linux等々
　[2.2] コンパイラ名 ： VC++ 2008EE, Borand C++, gcc等々

[3] その他
　・どの程度Ｃ言語を理解しているか
　・ライブラリを使っている場合は何を使っているか

[hr]

オフトピック

和の最大値が40、それぞれの数値が1以上なら全探索でも数日あれば答えが出そう…
とみせかけて、a[j]は整数とは限らないようなのである程度nが大きければ無限個が正解かな？

[YuO]

iとjの範囲に制限はないのでしょうか。
iとjに範囲があればa[j]は有限の値におさめる事ができますが，iとjに範囲がなければ，a[j]は無限を取り扱って処理しなければならなくなります。
# a[j]は整数と想定すると正の無限大に発散ですが。

問題文自体について(特に数式部分)，もう少し正確に記述してみてはいかがでしょうか。

[syakajin]

]

画像は
42
1
が抜けてしまっていますがn=7の場合です。

a[j]は整数です。

iとjは範囲設定が難しく困っています。
Σa[j] (任意のa[j]の足しあわせ)=n
a[j]≧1
a[j]>a[j+1]
a[j]>a[i+1][j]
の範囲を満たすように取りたいのですが、、、

[syakajin]

言語はcです。

[2] 環境 　
　[2.1] OS ： Windows,
　[2.2] コンパイラ名 ： gcc
です。

[かずま]

画像は
42
1
が抜けてしまっていますがn=7の場合です。

抜けているのは、[6 1], [5 2], [4 3] と [7] ではないのですか？

コード:

+---+---+  +---+---+  +---+---+  +---+---+  +---+  +---+  +---+
| 5 | 1 |  | 4 | 2 |  | 4 | 1 |  | 3 | 2 |  | 6 |  | 5 |  | 4 |
+---+---+  +---+---+  +---+---+  +---+---+  +---+  +---+  +---+
| 1 |      | 1 |      | 2 |      | 2 |      | 1 |  | 2 |  | 3 |
+---+      +---+      +---+      +---+      +---+  +---+  +---+

+---+---+  +---+---+  +---+---+  +---+
| 6 | 1 |  | 5 | 2 |  | 4 | 3 |  | 7 |
+---+---+  +---+---+  +---+---+  +---+

[かずま]

抜けているのは、[6 1], [5 2], [4 3] と [7] ではないのですか？

i が偶数という条件を忘れていました。失礼しました。でも、

コード:

+---+---+
| 4 | 2 |
+---+---+
| 1 |
+---+

は元の画像にありますよ。

[かずま]

抜けているのは、[6 1], [5 2], [4 3] と [7] ではないのですか？

n = 7 のとき、i が奇数なら、[4 2 1] の 1行と、それを縦に並べた 3行とが追加されますね。

コード:

+---+---+---+
| 4 | 2 | 1 |
+---+---+---+

+---+
| 4 |
+---+
| 2 |
+---+
| 1 |
+---+

[かずま]

n = 7、i が偶数で、まだ抜けがありました。

コード:

+---+---+---+
| 3 | 2 | 1 |
+---+---+---+
| 1 |
+---+

n = 7、i が奇数では、

コード:

+---+---+
| 3 | 1 |
+---+---+
| 2 |
+---+
| 1 |
+---+

手作業で抜けが生じるようでは、数え上げのアルゴリズムが確立しているとは
言えず、まだまだプログラムを書くところまでは行きませんね。

[かずま]

図を書くのは大変なので、改行を表す / を導入し、[a b/c d] のような記法を使います。
/ が 0個だと 1行で奇数、/ が 1個だと 2行で偶数、/ が 2個だと 3行で奇数となります。

コード:

n = 1:
    [1]    奇数 1, 偶数 0
n = 2:
    [2]    奇数 1, 偶数 0
n = 3:
    [3], [2 1]　奇数 2
    [2/1]       偶数 1
n = 4:
    [4], [3 1]      奇数 2
    [3/1], [2 1/1]  偶数 2
n = 5:
    [5], [4 1], [3 2]      奇数 3
    [4/1], [3/2], [3 1/1]  偶数 3	　
n = 6:
    [6], [5 1], [4 2], [3 2 1], [3/2/1]      奇数 5
    [5/1], [4/2], [4 1/1], [3 2/1], [3 1/2]  偶数 5
n = 7:
    [7], [6 1], [5 2], [4 3], [4 2 1], [4/2/1], [3 1/2/1]               奇数 7
    [6/1], [5/2], [4/3], [5 1/1], [4 2/1], [4 1/2], [3 2/2], [3 2 1/1]  偶数 8
n = 8:
    [8], [7 1], [6 2], [5 3], [5 2 1], [4 3 1],
	    [5/2/1], [4/3/1], [3 2/2/1]                      奇数 9
    [7/1], [6/2], [5/3], [6 1/1], [5 2/1], [5 1/2],
	    [4 3/1], [4 1/3], [4 2/2], [3 2/2 1], [3 2 1/2]  偶数 11

抜けはありませんか？

[みけCAT]

プログラムを書いてみようと思いましたが、条件がわかりません。

• iの最小値に規定はありますか？
• i, jは整数に限りますか？
• a[j]が存在しうる時、a[j]を作らずにa[j+1]やa[i+1][j]を作ることはできますか？

[みけCAT]

とりあえず

• i, jは1以上の整数
• a[j]が存在できる場合、a[j]がないのにa[j+1]やa[i+1][j]があってはいけない

と仮定して、普通に全探索するプログラムを書いてみました。
n = 40のとき、2.5秒程度で処理が終わりました。(Intel(R) Core(TM) i7-4712MQ CPU @ 2.30GHz 2.30GHz)

n = 10のとき、偶数26個、奇数23個
n = 20のとき、偶数733個、奇数730個
n = 30のとき、偶数13641個、奇数13945個
n = 40のとき、偶数194125個、奇数195902個
と出ました。

コード:

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

int odd_count = 0, even_count = 0;

int n;
int* data;

void search(int i, int j, int n_left) {
	if (n_left <= 0) {
		int y, x;
		data[i * n + j] = 0;
		putchar('[');
		for (y = 0; y <= i; y++) {
			for (x = 0; data[y * n + x] > 0; x++) {
				if (x > 0) putchar(' ');
				printf("%d", data[y * n + x]);
			}
			if (y < i) putchar('/');
		}
		putchar(']');
		printf(" : %s\n", i % 2 == 1 ? "even" : "odd");
		if (i % 2 == 1) even_count++; else odd_count++;
	} else {
		int c;
		/* ここで次の行に行ってみる */
		if (j > 0) {
			data[i * n + j] = 0;
			search(i + 1, 0, n_left);
		}
		/* 今いる行で続ける */
		for (c = 1; c <= n_left &&
		(i == 0 || c < data[(i - 1) * n + j]) && (j == 0 || c < data[i * n + (j - 1)]); c++) {
			data[i * n + j] = c;
			search(i, j + 1, n_left - c);
		}
	}
}

int main(void) {
	if (scanf("%d", &n) != 1) return 1;
	data = malloc(sizeof(int) * n * n);
	if (data == NULL) return 1;
	search(0, 0, n);
	printf("even = %d, odd = %d\n", even_count, odd_count);
	free(data);
	return 0;
}

抜けはありませんか？

n=8のとき、[4 1/2/1] (奇数) と[4 2 1/1] (偶数) が抜けているようですね。

[YuO]

]

この一番左上，[5 1/1]の例について，

• a[1][1] = 5
• a[1][2] = 1
• a[2][1] = 1

だと思うのですが，a[1][2] > a[1][3] ≧ 1を満たしません。

オフトピック

任意のi, jに対して，a[j] ≧ 1かつa[j] > a[j + 1]だから，a[j] > [j + 1] ≧ 1。
i = 1, j = 2とすると，上記の式が出る。

これはよいのでしょうか。

i,jの範囲に対する制限がないので，このようなことが起きています。

[syakajin]

かずまさん、抜けの指摘、書き表し方のアドバイスありがとうございました。
初の投稿で要領がつかめていませんでした。精進します。


みけCATさん、どうもありがとうございます。
•i, jは1以上の整数
•a[j]が存在できる場合、a[j]がないのにa[j+1]やa[i+1][j]があってはいけない
が必要な条件でした。

画像の抜けも申し訳ありませんでした。お世話になりました。
明日、実際にプログラムを動かしてみて確認します。

[syakajin]

みけCATさん
n = 10のとき、偶数26個、奇数23個　　今、手で数えてみましたが求めたい数を返してくれているようです。

[syakajin]

みけCATさん
n = 10のとき、偶数26個、奇数23個　　今、手で数えてみましたが求めたい数を返してくれているようです。

[syakajin]

みけCATさん、プログラム確認しました。どうもありがとうございます。

続けて質問してもいいでしょうか。

条件にイコールを加えて、
Σa[j] (任意のa[j]の足しあわせ)=n
a[j]≧1
a[j]>=a[j+1]
a[j]>=a[i+1][j]

とした場合はどのようにプログラムを書き直せばよいのですか。

[syakajin]

みけCATさん、プログラム確認しました。どうもありがとうございます。

続けて質問してもいいでしょうか。

条件にイコールを加えて、
Σa[j] (任意のa[j]の足しあわせ)=n
a[j]≧1
a[j]>=a[j+1]
a[j]>=a[i+1][j]

とした場合はどのようにプログラムを書き直せばよいのですか。

[syakajin]

また、
Σa[j] (任意のa[j]の足しあわせ)=n
a[j]≧1
a[j]>=a[j+1]
a[j]>a[i+1][j]
の場合はどうでしょうか。

[みけCAT]

条件にイコールを加えて、
Σa[j] (任意のa[j]の足しあわせ)=n
a[j]≧1
a[j]>=a[j+1]
a[j]>=a[i+1][j]

とした場合はどのようにプログラムを書き直せばよいのですか。

条件式を条件に合わせて書き直せばいいです。

コード:

(i == 0 || c < data[(i - 1) * n + j]) && (j == 0 || c < data[i * n + (j - 1)])

↓

コード:

(i == 0 || c <= data[(i - 1) * n + j]) && (j == 0 || c <= data[i * n + (j - 1)])

また、
Σa[j] (任意のa[j]の足しあわせ)=n
a[j]≧1
a[j]>=a[j+1]
a[j]>a[i+1][j]
の場合はどうでしょうか。

コード:

(i == 0 || c < data[(i - 1) * n + j]) && (j == 0 || c < data[i * n + (j - 1)])

↓

コード:

(i == 0 || c < data[(i - 1) * n + j]) && (j == 0 || c <= data[i * n + (j - 1)])

[syakajin]

ありがとうございます！完全に解決しました！