プログラマ専用SNS ミクプラ

こんにちは。

配列 array[20] =
{1, 2, 5, 6
4, 2, 3, 7
2, 1, 9, 10
10, 3, 7, 4
8, 7, 6, 0 }

という配列arrayについて、2つの数値のペアを探し出す、という問題があるのですが、考えてもやり方が分かりません。

ペアを探し出すというのは、arrayの中に隣り合った番号の組がいくつあるか、というものです。
例えば、arrayでいうと「1, 2」を1と2のペアだとみなし、順にサーチしていき、「2, 1」があるので「1と2のペアは全部で2組ある」と出力するものです。

「1, 2」と「2, 1」は同じだとみなして構いません（順不同）。

「1, 2」が終われば次は「2, 5」、「5, 6」、「6,1」、「6, 4」とそれぞれペアをサーチしていきます。

どなたかこのアルゴリズムを分かる方いらっしゃいませんか？
よろしくお願いします。

せいじさんが書きました: ペアを探し出すというのは、arrayの中に隣り合った番号の組がいくつあるか、というものです。

隣り合った番号の組の定義がよくわかりません。

せいじさんが書きました: 配列 array[20] =
{1, 2, 5, 6
4, 2, 3, 7
2, 1, 9, 10
10, 3, 7, 4
8, 7, 6, 0 }
「1, 2」が終われば次は「2, 5」、「5, 6」、「6,1」、「6, 4」とそれぞれペアをサーチしていきます。

「6, 1」？これがどこから出てきたのかわかりません。

arrayを1次元配列ではなくて、リングバッファの集まりとした方がよかったですね。言葉足らずでした。すいません。

リングバッファ1　[1,2,5,6]
リングバッファ2　[4,2,3,7]
リングバッファ3　[2,1,9,10]
リングバッファ4　[10,3,7,4]
リングバッファ5　[8,7,6,0]

と5つのリングバッファを考えた時、リングバッファ1における隣り合った番号の組は[1 2],[2,5],[5,6],[6,1]となりますよね？
リングバッファ1の[1,2]（[2,1]も等価とみなす）が他のリングバッファにあるかサーチしていき、リングバッファ3に[2,1]があるので、「[1,2]はペアが存在」と考えます。

次に[2,5]についてサーチしていきますが、[2,5]および[5,2]は他に見つからないので「[2,5]はペアが存在せず」と考えます。

これを[5,6],[6,1]、リングバッファ2にうつり[4,2],[2,3],[3,7],[7,4]と同じようにサーチしていきます。

こんな説明でよろしいでしょうか？
うまく伝えるのはなかなか難しいなと再認識しました。

pair を map に入れるだけなのでは？

コード:

#include <iostream>
#include <map>
using namespace std;

const int ROW = 5, COL = 4;

int array[ROW][COL] = {
    { 1, 2, 5, 6 },
    { 4, 2, 3, 7 },
    { 2, 1, 9, 10},
    {10, 3, 7, 4 },
    { 8, 7, 6, 0 },
};

int main(void)
{
    typedef map<pair<int, int>, int> Map;
    Map m;
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++) {
            int a = array[i][j];
            int b = array[i][(j + 1) % COL];
            if (a < b) m[make_pair(a, b)]++;
            else m[make_pair(b, a)]++;
        }
    for (Map::const_iterator it = m.begin(); it != m.end(); ++it)
        cout << "[" << it->first.first << ", "
             << it->first.second << "] : " << it->second << endl;
}

実行結果

コード:

[0, 6] : 1
[0, 8] : 1
[1, 2] : 2
[1, 6] : 1
[1, 9] : 1
[2, 3] : 1
[2, 4] : 1
[2, 5] : 1
[2, 10] : 1
[3, 7] : 2
[3, 10] : 1
[4, 7] : 2
[4, 10] : 1
[5, 6] : 1
[6, 7] : 1
[7, 8] : 1
[9, 10] : 1

データが以下の場合、(2, 5)はペアとみなしますか？

{ 1, 2, 5, 2 },
{ 4, 2, 3, 7 },
{ 2, 1, 9, 10},
{10, 3, 7, 4 },
{ 8, 7, 6, 0 },

かずま様

mapなんてものがあったんですね...
知りませんでした。
使い方等勉強してみようと思います。

たいちう様

ペアとみなしてもらって構いません。
その例だと、(2,5)ペアは2組(2,5),(5,2)存在するということになります。

> ペアとみなしてもらって構いません。

そうですか。
「他のリングバッファにあるかサーチしていき」とあったので気になったのですが、
ペアでよいなら、かずまさんのプログラムで完璧ですね。

かずまさんが書きました:pair を map に入れるだけなのでは？

コード:

#include <iostream>
#include <map>
using namespace std;

const int ROW = 5, COL = 4;

int array[ROW][COL] = {
    { 1, 2, 5, 6 },
    { 4, 2, 3, 7 },
    { 2, 1, 9, 10},
    {10, 3, 7, 4 },
    { 8, 7, 6, 0 },
};

int main(void)
{
    typedef map<pair<int, int>, int> Map;
    Map m;
    for (int i = 0; i < ROW; i++)
        for (int j = 0; j < COL; j++) {
            int a = array[i][j];
            int b = array[i][(j + 1) % COL];
            if (a < b) m[make_pair(a, b)]++;
            else m[make_pair(b, a)]++;
        }
    for (Map::const_iterator it = m.begin(); it != m.end(); ++it)
        cout << "[" << it->first.first << ", "
             << it->first.second << "] : " << it->second << endl;
}

実行結果

コード:

[0, 6] : 1
[0, 8] : 1
[1, 2] : 2
[1, 6] : 1
[1, 9] : 1
[2, 3] : 1
[2, 4] : 1
[2, 5] : 1
[2, 10] : 1
[3, 7] : 2
[3, 10] : 1
[4, 7] : 2
[4, 10] : 1
[5, 6] : 1
[6, 7] : 1
[7, 8] : 1
[9, 10] : 1

このプログラムの

if (a < b) m[make_pair(a, b)]++;
else m[make_pair(b, a)]++;
}
for (Map::const_iterator it = m.begin(); it != m.end(); ++it)
cout << "[" << it->first.first << ", "
<< it->first.second << "] : " << it->second << endl;
}

の部分ですが、これはC言語で言うとどのような処理をしているのでしょうか？
C言語しか習っておらず、C++はよく分かっていない状態です。

たいちう様

私の書き方がよろしくなかったですね。
反省します。

> の部分ですが、これはC言語で言うとどのような処理をしているのでしょうか？
> C言語しか習っておらず、C++はよく分かっていない状態です。

C++のライブラリを使っています。
「stl map」でググりましょう。

C言語には該当するライブラリがないので、同等のものを自作する必要があります。
(探せばあるかもしれませんが)
その場合は難易度が少し上がりますが、C言語で作成しますか?

> 私の書き方がよろしくなかったですね。
> 反省します。

仕様を正確に文章にするのはプロにも難しいものです。
でも、これが書けないとプログラムは尚更書けないので、頑張ってください。

たいちうさんが書きました:> の部分ですが、これはC言語で言うとどのような処理をしているのでしょうか？
> C言語しか習っておらず、C++はよく分かっていない状態です。

C++のライブラリを使っています。
「stl map」でググりましょう。

C言語には該当するライブラリがないので、同等のものを自作する必要があります。
(探せばあるかもしれませんが)
その場合は難易度が少し上がりますが、C言語で作成しますか?

> 私の書き方がよろしくなかったですね。
> 反省します。

仕様を正確に文章にするのはプロにも難しいものです。
でも、これが書けないとプログラムは尚更書けないので、頑張ってください。

たいちう様

それでしたら、もうこの際に勉強と思ってC++についても学習してみようかなと思います。
C言語で作成しようと思っていたのですが、C++の方がこの場合は簡単なようなので、C++にします。

ありがとうございます。
色々と頑張っていきたいと思います。

結果がペアの昇順になっていなくてもよければ簡単に C で書けますよ。

コード:

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

#define ROW 5
#define COL 4

int array[ROW][COL] = {
    { 1, 2, 5, 6 },
    { 4, 2, 3, 7 },
    { 2, 1, 9, 10},
    {10, 3, 7, 4 },
    { 8, 7, 6, 0 },
};

int t[ROW * COL + 1][3];
int size = 0;

void add(int a, int b)
{
    int i;
    t[size][0] = a,  t[size][1] = b,  t[size][2] = 0;
    for (i = 0; t[i][0] != a || t[i][1] != b; i++) ;
    t[i][2]++;
    if (i == size) size++;
}

int main(void)
{
    int i, j;
    for (i = 0; i < ROW; i++)
        for (j = 0; j < COL; j++) {
            int a = array[i][j];
            int b = array[i][(j + 1) % COL];
            if (a < b) add(a, b);
            else add(b, a);
        }
    for (i = 0; i < size; i++)
        printf("[%d, %d] : %d\n", t[i][0], t[i][1], t[i][2]);
    return 0;
}

ソート版も必要ですか？

考えてみたら、C++を覚える方がよほど難易度が高いですね。
数値の範囲を決めてよいならば、次のプログラムで十分です。

コード:

#include <stdio.h>
 
#define ROW 5
#define COL 4
#define MAX_NUM 10

int array[ROW][COL] = {
    { 1, 2, 5, 6 },
    { 4, 2, 3, 7 },
    { 2, 1, 9, 10},
    {10, 3, 7, 4 },
    { 8, 7, 6, 0 },
};
 
int main() {
	int m[MAX_NUM + 1][MAX_NUM + 1] = { 0 };
	int i, j, a, b;
    for (i = 0; i < ROW; i++)
        for (j = 0; j < COL; j++) {
            a = array[i][j];
            b = array[i][(j + 1) % COL];
            if (a < b) m[a][b] = m[a][b] + 1;
            else m[b][a] = m[b][a] + 1;
        }
    for (i = 0; i < MAX_NUM + 1; i++)
        for (j = i; j < MAX_NUM + 1; j++)
			if (m[i][j] > 0) {
				printf("[%d, %d] : %d\n", i, j, m[i][j]);
			}
	return 0;
}

かずまさんに先を越されてしまった。勉強になります。

ところで、15行目で、+1 は必要ですか?
sizeが最大になるのは、全ての数値が違う場合で、ROW*COL だと思うのですが。

たいちうさんが書きました:ところで、15行目で、+1 は必要ですか?
sizeが最大になるのは、全ての数値が違う場合で、ROW*COL だと思うのですが。

はい、その通りです。+1 は不要です。

ペアが表に登録済みかどうか探索するとき、ループの終了条件が
(1)途中で見つかるか、
(2)最後まで行くか、
の 2つになるのを、最後にペアを番兵として置くことで、
ループの終了条件を 1つにできます。
その番兵を置くために +1個余分に要ると勘違いしました。

たいちうさんのプログラムは、データの最大値が大きいと、データの個数に比べて
とても大きなメモリを必要としますが、カウントアップは高速ですね。
結果もソートされていて、この問題に関してはいいものだと思います。

さて、結果がソートされるプログラムを私も書いてみました。

コード:

#include <stdio.h>   // printf
#include <stdlib.h>  // exit
#include <string.h>  // memmove

#define ROW 5
#define COL 4

int array[ROW][COL] = {
    { 1, 2, 5, 6 },
    { 4, 2, 3, 7 },
    { 2, 1, 9, 10},
    {10, 3, 7, 4 },
    { 8, 7, 6, 0 },
};

int t[ROW * COL + 1][3];
int size = 0;

void add(int a, int b)
{
    int i;
    for (i = 0; i < size; i++) {
        if (t[i][0] > a) break;
        if (t[i][0] == a) {
            if (t[i][1] == b) { t[i][2]++; return; }
            if (t[i][1] > b) break;
        }
    }
    memmove(t[i+1], t[i], sizeof(int[3]) * (size - i));
    size++;
    t[i][0] = a,  t[i][1] = b,  t[i][2] = 1;
}

int main(void)
{
    int i, j;
    for (i = 0; i < ROW; i++)
        for (j = 0; j < COL; j++) {
            int a = array[i][j];
            int b = array[i][(j + 1) % COL];
            if (a < b) add(a, b);
            else add(b, a);
        }
    for (i = 0; i < size; i++)
        printf("[%d, %d] : %d\n", t[i][0], t[i][1], t[i][2]);
    return 0;
}

返信が遅くなりました。

少し見ていない間に、二人とも色々書いてくださり、本当にありがとうございます！
問題も無事解けました。
今後、時間に余裕のある時にCとC++を勉強していきたいと思います。

プログラマ専用SNS ミクプラ

配列に格納された数値のペアを探し出す

配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す

Re: 配列に格納された数値のペアを探し出す