掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.29466

魔方陣について
投稿者---hemu(2007/01/17 16:29:52)


7×7の魔方陣を表示するプログラムを作るのが目的です。
いちおう頑張って表示するプログラムを作ったんですが、自分の作ったプログラムでは1種類しか表示することができないことに気づきました。
すべての種類の魔方陣を表示するプログラムはまた根本的に違うものなのでしょうか??
誰か教えてください。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:魔方陣について 29468 ぽへぇ 2007/01/17 18:42:50


No.29468

Re:魔方陣について
投稿者---ぽへぇ(2007/01/17 18:42:50)


どうしてソースを添付しないんですか?
>根本的に違うもの
かどうか判断できないのですが。

こちらもどうぞ。
http://ja.wikipedia.org/wiki/%E9%AD%94%E6%96%B9%E9%99%A3



この投稿にコメントする

削除パスワード

No.29474

Re:魔方陣について
投稿者---hemu(2007/01/18 16:20:53)


#include<stdio.h>

void main()
{
static int mg[16][16],ii=1,jj,nn,kk;

printf("15以下の奇数を入力してください!\n");
scanf("%d",&nn);
jj=(nn+1)/2;
mg[1][jj]=1;
for(kk=2;kk<=nn*nn;kk++){
if(kk%nn==1)
ii++;
else if(ii==1){
ii=nn;
jj++;
}
else if(jj==nn){
ii--;
jj=1;
}
else {
ii--;
jj++;
}
mg[ii][jj]=kk;
}
for(ii=1;ii<=nn;ii++){
printf("\n");
for(jj=1;jj<=nn;jj++)
printf("%5d",mg[ii][jj]);
}
}

たとえばこれなんですが。これは一種類しか表示されませんよね。
これを全部表示するプログラムに変えることはできますか?


この投稿にコメントする

削除パスワード

No.29480

Re:魔方陣について
投稿者---ももん(2007/01/18 19:14:13)


入力された値が
偶数か奇数かによって
違う手法で作成すればいい


この投稿にコメントする

削除パスワード

No.29481

Re:魔方陣について
投稿者---たいちう(2007/01/18 19:27:30)


全ての数字の置き方を試してみる以外には、
魔方陣の総数を求める方法は知られていません。

魔方陣の次数(7×7ならば7次)が増えると組み合わせは
天文学的数字になり、現在の市販のパソコンの限界は5次でしょう。
プログラムの巧拙もありますが、手軽なのは3次と4次のみ。

また総数が求められているのは5次までで、
6次の総数は、約1,700京になると予想されているようです。

http://mathworld.wolfram.com/MagicSquare.html
http://www.heart.ne.jp/~issei/msqj/5houjin2.htm


ですので、

> これを全部表示するプログラムに変えることはできますか?

変えるというよりは、全て作り直すことになります。
また現実的な時間内で総数を出せるのは5次までです。


この投稿にコメントする

削除パスワード

No.29617

Re:魔方陣について
投稿者---ぽへぇ(2007/01/27 12:09:39)


全列挙です。生半可に枝刈りをしてみましたが、
このくらいでは 5 <= n ですでに使い物になりません orz
せっかくなので貼っておきます。^^;

#include<stdio.h>

#define NO   (0)
#define YES  (1)

int perm(int depth);

int checkY(int y);
int checkCross(void);

int n;
int nn;      // n^2
int used[16*16];
int a[16*16];        // 仮の魔方陣
int TargetSum;      // 目的の合計値
int count;

void main()
{
    printf("15以下の数を入力してください:");
    scanf("%d", &n);
    nn = n*n;
    // どの 列, 行, 対角の和も(n^3+n)/2になるはず
    TargetSum = (nn*n + n)/2;

    perm(0);
}

// 組み合わせ生成
int perm(int depth)
{
    if (depth == nn) {
        int x, y;
        // 対角線チェック
        if (!checkCross()) return 0;
        // 表示
        count++;
        printf("%5d個目\n", count);
        for (y = 0; y < n; y++) {
            for (x = 0; x < n; x++) {
                printf("%5d", a[y*n+x]);
            }
            printf("\n");
        }
        return  1;
    } else {
        int u;
        for (u = 0; u < nn; u++) {
            if (used[u] == NO) {
                a[depth] = u+1;

                if (((depth+1)%n) == 0) {
                    // 枝刈り 深さがnの倍数になったので 深さ/n 行目がチェック可能
                    int x, y;
                    int breakf = NO;
                    // その1: 行の合計が目的と一致しなければ抜ける
                    const int targetY = depth/n;
                    if (!checkY(targetY)) {
                        continue;
                    }
                    // その2: 列の合計が目的よりも大きくなったら抜ける
                    for (x = 0; x < n; x++) {
                        int sum = 0;
                        for (y = 0; y <= targetY; y++) {
                            sum += a[y*n+x];
                            if (TargetSum < sum) {
                                breakf = YES;
                                break;
                            }
                        }
                        if (breakf) break;
                    }
                    if (breakf) {
                        continue;
                    }
                }
                // 生き残ったので探索を続ける
                used[u] = YES;
                perm(depth + 1);
                used[u] = NO;
            }
        }
        return 0;
    }
}

// y行目の正当性を調べる
int checkY(int y)
{
    int x, sum = 0;
    for (x = 0; x < n; x++) {
        sum += a[y*n+x];
    }
    if (sum == TargetSum) return 1;
    return 0;
}

// 対角線を調べる
int checkCross(void)
{
    int suma = 0;
    int sumb = 0;
    int xy;

    for (xy = 0; xy < n; xy++) {
        suma += a[xy*n + xy];
        sumb += a[xy*n + (n-1) -xy];
    }
    if (suma != TargetSum) return 0;
    if (sumb != TargetSum) return 0;
    return 1;
}



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧