状態数の数え上げについて

[mkai]

fはx,y,zの3つの変数を持つ関数とします。
ただし、x,y,zはぞれぞれ整数で0≦x,y,z≦Nとします。
ここで、x,yが等しくzを0≦z≦Nの範囲で変えたものを1セットの状態として状態の数(状態数)を数えていきます。
ただし、任意のzにおいて、x,yが異なっていてもfの出力結果が等しいものを同一とみなします。
例えばN=1の時
f[0,0,0]=0、f[0,0,1]=0…(1)
f[0,1,0]=0、f[0,1,1]=1…(2)
f[1,0,0]=1、f[1,0,1]=1…(3)
f[1,1,0]=0、f[1,1,1]=1…(4)
と言う結果が得られたとすると、本来状態数は4ですが、(2)と(4)の出力結果はz=0の時0、z=1の時1を出力するので同一とみなし、状態数は3です。
N=2の時は
f[0,0,0]=0、f[0,0,1]=0、f[0,0,2]=0…(1)
f[0,1,0]=0、f[0,1,1]=0、f[0,1,2]=1…(2)
f[0,2,0]=1、f[0,2,1]=1、f[0,2,2]=2…(3)
f[1,0,0]=1、f[1,0,1]=1、f[1,0,2]=1…(4)
f[1,1,0]=1、f[1,1,1]=1、f[1,1,2]=0…(5)
f[1,2,0]=1、f[1,2,1]=1、f[1,2,2]=2…(6)
f[2,0,0]=2、f[2,0,1]=2、f[2,0,2]=2…(7)
f[2,1,0]=1、f[2,1,1]=1、f[2,1,2]=0…(8)
f[2,2,0]=1、f[2,2,1]=1、f[2,2,2]=2…(9)
と言う結果が得られたとすると、本来状態数は9ですが、(3)と(6)と(9)はz=0,1で1を、z=2で2を出力し、また(5)と(8)はz=0,1で1を、z=2で0を出力するので同一とみなし状態数は6となります。

このように状態数を数え上げるプログラムを作りたいのですがどのように作ればいいのか分かりません。
分かりづらいかもしれませんが宜しくお願いします。

[ookami]

問題そのものは分かりましたが、プログラムへの入力がよく分かりません。
(1)～(9)は手動で計算してプログラムに直書きでしょうか？

どちらにしても、数え上げる部分はプログラムするんだと思うので、
まずは以下のようなプログラムから始めてはいかがでしょうか。

(1)～(9)を配列等に格納し、

(1)と(2)が等しいかチェック
(1)と(3)が等しいかチェック
(1)と(4)が等しいかチェック
　　：
(1)と(9)が等しいかチェック

(2)と(3)が等しいかチェック
(2)と(4)が等しいかチェック
(2)と(5)が等しいかチェック
　　：
(2)と(9)が等しいかチェック

(3)と(4)が等しいかチェック
(3)と(5)が等しいかチェック
(3)と(6)が等しいかチェック
　　：
(3)と(9)が等しいかチェック

　　：

(8)と(9)が等しいかチェック
チェック完了後、等しい判定が出た回数だけ全体の数から引かれていればよい。

[かずま]

入力データの形式を次のようにすると、C++ では簡単になります。

コード:

1
0,0
0,1
1,1
0,1

2
0,0,0
0,0,1
1,1,2
1,1,1
1,1,0
1,1,2
2,2,2
1,1,0
1,1,2

コード:

#include <iostream>
#include <string>
#include <map>

int main()
{
    using namespace std;
    while (1) {
        int n;
        cin >> n;
        if (!cin || n <= 0) break;
        int k = (n + 1) * (n + 1);
        map<string, int> m;
        while (--k >= 0) {
            string s;
            cin >> s;
            if (!cin) return 1;
            m[s]++;
        }
        cout << "N = " << n << ", number of states = " << m.size() << endl;
    }
}

実行結果

コード:

N = 1, number of states = 3
N = 2, number of states = 6

[mkai]

ookamiさん、返信ありがとうございます。

> 問題そのものは分かりましたが、プログラムへの入力がよく分かりません。
> (1)～(9)は手動で計算してプログラムに直書きでしょうか？

申し訳ありません。関係ないと思って端折りましたが、3変数はfor文で入力して、出力結果はある計算式から導出しています。
具体的に言うと(少し違いますが)
f[x][y][z] = y + min(N-y,x) - min(N-z,y)
です。

if文とfor文を用いてそのようにしようとは思ったのですが
f[1][1][1]とf[1][2][1]を比較など一部はできるのですが、どうも(1)と(3)などを任意のzに対しての比較がどうすればいいのか分からなくて…

かずまさん
返信ありがとうございます。
ありがとうございます！ちなみにこれをCで簡単に書く事は出来ないのでしょうか…？
不勉強でC++のプログラムの意味がよく分からないので出来ればCで書きたいのです。；

色々と文句ばかり申し訳ありません。

[かずま]

ちなみにこれをCで簡単に書く事は出来ないのでしょうか…？

コード:

#include <stdio.h>
#include <string.h>
 
#define N 99

int main(void)
{
    static char *m[(N + 1) * (N + 1)], s[100];
    int n, k, i, c;

    while (scanf("%d", &n) == 1 && n > 0 && n <= N) {
        for (k = (n + 1) * (n + 1), c = 0; --k >= 0; ) {
            if (scanf("%99s", s) != 1) return 1;
            for (i = 0; i < c && strcmp(m[i], s); i++) ;
            if (i == c) m[c++] = strdup(s);
        }
        printf("N = %d, number of states = %d\n", n, c);
    }
    return 0;
}

[かずま]

printf() 前に(後でもいいけど)、次の 1行を追加してください。

コード:

        for (i = 0; i < c; i++) free(m[i]);

[mkai]

かずまさん
遅くなって申し訳ありません。返信ありがとうございます。
申し訳ありません；
プログラムの意味がわからないところが多々あるので、今一度勉強し直してかずまさんが書いてくださったコードを元に作成してみようと思います。
ありがとうございました！