配列に格納された数値のペアを探し出す
配列に格納された数値のペアを探し出す
こんにちは。
配列 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[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」とそれぞれペアをサーチしていきます。
どなたかこのアルゴリズムを分かる方いらっしゃいませんか?
よろしくお願いします。
Re: 配列に格納された数値のペアを探し出す
隣り合った番号の組の定義がよくわかりません。せいじ さんが書きました: ペアを探し出すというのは、arrayの中に隣り合った番号の組がいくつあるか、というものです。
「6, 1」?これがどこから出てきたのかわかりません。せいじ さんが書きました: 配列 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」とそれぞれペアをサーチしていきます。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。
Re: 配列に格納された数値のペアを探し出す
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]と同じようにサーチしていきます。
こんな説明でよろしいでしょうか?
うまく伝えるのはなかなか難しいなと再認識しました。
リングバッファ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]と同じようにサーチしていきます。
こんな説明でよろしいでしょうか?
うまく伝えるのはなかなか難しいなと再認識しました。
Re: 配列に格納された数値のペアを探し出す
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;
}
Re: 配列に格納された数値のペアを探し出す
データが以下の場合、(2, 5)はペアとみなしますか?
{ 1, 2, 5, 2 },
{ 4, 2, 3, 7 },
{ 2, 1, 9, 10},
{10, 3, 7, 4 },
{ 8, 7, 6, 0 },
{ 1, 2, 5, 2 },
{ 4, 2, 3, 7 },
{ 2, 1, 9, 10},
{10, 3, 7, 4 },
{ 8, 7, 6, 0 },
Re: 配列に格納された数値のペアを探し出す
かずま様
mapなんてものがあったんですね...
知りませんでした。
使い方等勉強してみようと思います。
たいちう様
ペアとみなしてもらって構いません。
その例だと、(2,5)ペアは2組(2,5),(5,2)存在するということになります。
mapなんてものがあったんですね...
知りませんでした。
使い方等勉強してみようと思います。
たいちう様
ペアとみなしてもらって構いません。
その例だと、(2,5)ペアは2組(2,5),(5,2)存在するということになります。
Re: 配列に格納された数値のペアを探し出す
> ペアとみなしてもらって構いません。
そうですか。
「他のリングバッファにあるかサーチしていき」とあったので気になったのですが、
ペアでよいなら、かずまさんのプログラムで完璧ですね。
そうですか。
「他のリングバッファにあるかサーチしていき」とあったので気になったのですが、
ペアでよいなら、かずまさんのプログラムで完璧ですね。
Re: 配列に格納された数値のペアを探し出す
このプログラムのかずま さんが書きました: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; }
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++はよく分かっていない状態です。
Re: 配列に格納された数値のペアを探し出す
> の部分ですが、これはC言語で言うとどのような処理をしているのでしょうか?
> C言語しか習っておらず、C++はよく分かっていない状態です。
C++のライブラリを使っています。
「stl map」でググりましょう。
C言語には該当するライブラリがないので、同等のものを自作する必要があります。
(探せばあるかもしれませんが)
その場合は難易度が少し上がりますが、C言語で作成しますか?
> 私の書き方がよろしくなかったですね。
> 反省します。
仕様を正確に文章にするのはプロにも難しいものです。
でも、これが書けないとプログラムは尚更書けないので、頑張ってください。
> C言語しか習っておらず、C++はよく分かっていない状態です。
C++のライブラリを使っています。
「stl map」でググりましょう。
C言語には該当するライブラリがないので、同等のものを自作する必要があります。
(探せばあるかもしれませんが)
その場合は難易度が少し上がりますが、C言語で作成しますか?
> 私の書き方がよろしくなかったですね。
> 反省します。
仕様を正確に文章にするのはプロにも難しいものです。
でも、これが書けないとプログラムは尚更書けないので、頑張ってください。
Re: 配列に格納された数値のペアを探し出す
たいちう さんが書きました:> の部分ですが、これはC言語で言うとどのような処理をしているのでしょうか?
> C言語しか習っておらず、C++はよく分かっていない状態です。
C++のライブラリを使っています。
「stl map」でググりましょう。
C言語には該当するライブラリがないので、同等のものを自作する必要があります。
(探せばあるかもしれませんが)
その場合は難易度が少し上がりますが、C言語で作成しますか?
> 私の書き方がよろしくなかったですね。
> 反省します。
仕様を正確に文章にするのはプロにも難しいものです。
でも、これが書けないとプログラムは尚更書けないので、頑張ってください。
たいちう様
それでしたら、もうこの際に勉強と思ってC++についても学習してみようかなと思います。
C言語で作成しようと思っていたのですが、C++の方がこの場合は簡単なようなので、C++にします。
ありがとうございます。
色々と頑張っていきたいと思います。
Re: 配列に格納された数値のペアを探し出す
結果がペアの昇順になっていなくてもよければ簡単に 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;
}
Re: 配列に格納された数値のペアを探し出す
考えてみたら、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;
}
Re: 配列に格納された数値のペアを探し出す
かずまさんに先を越されてしまった。勉強になります。
ところで、15行目で、+1 は必要ですか?
sizeが最大になるのは、全ての数値が違う場合で、ROW*COL だと思うのですが。
ところで、15行目で、+1 は必要ですか?
sizeが最大になるのは、全ての数値が違う場合で、ROW*COL だと思うのですが。
Re: 配列に格納された数値のペアを探し出す
はい、その通りです。+1 は不要です。たいちう さんが書きました:ところで、15行目で、+1 は必要ですか?
sizeが最大になるのは、全ての数値が違う場合で、ROW*COL だと思うのですが。
ペアが表に登録済みかどうか探索するとき、ループの終了条件が
(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;
}
Re: 配列に格納された数値のペアを探し出す
返信が遅くなりました。
少し見ていない間に、二人とも色々書いてくださり、本当にありがとうございます!
問題も無事解けました。
今後、時間に余裕のある時にCとC++を勉強していきたいと思います。
少し見ていない間に、二人とも色々書いてくださり、本当にありがとうございます!
問題も無事解けました。
今後、時間に余裕のある時にCとC++を勉強していきたいと思います。