今、a+b+cから
a+b+c
a+c+b
b+a+c
b+c+a
c+a+b
c+b+a
と全ての項を入れ替えたパターンを生成するプログラムを考えているのですが、全く考えつかず困っています。
こういう方法だったらできるかもしれないといった、確信がないアドバイスでも頂ければ嬉しいです。
足し算の項の入れ替え
Re: 足し算の項の入れ替え
パターンを生成する部分は、C++のstd::next_permutationを使うと簡単でしょう。
#include <iostream>
#include <algorithm>
int main(void) {
const int num = 3;
int order[] = {0, 1, 2};
char data[] = "abc";
do {
std::cout << data[order[0]];
for (int i = 1; i < num; i++) {
std::cout << '+' << data[order[i]];
}
std::cout << '\n';
} while (std::next_permutation(order, order + 3));
return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 足し算の項の入れ替え
入力を受け取る部分も作ってみました。
入力例1
出力例1
入力例2
出力例2
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
int main(void) {
std::vector<int> order;
std::vector<std::string> data;
std::string input;
// 入力を読み込む
if (!std::getline(std::cin, input)) {
std::cerr << "read error\n";
return 1;
}
// input.c_str()をそのままデータの書換えを行うstrtok()に渡すとまずいので、コピーする
char* c_input = new char[input.length() + 1];
strcpy(c_input, input.c_str());
// 入力を"+"で分割する
char* one_data = strtok(c_input, "+");
do {
order.push_back(order.size());
data.push_back(one_data);
} while ((one_data = strtok(NULL, "+")) != NULL);
delete[] c_input;
// パターンを生成する
do {
for (std::vector<int>::iterator it = order.begin(); it != order.end(); it++) {
if (it != order.begin()) std::cout << '+';
std::cout << data[*it];
}
std::cout << '\n';
} while (std::next_permutation(order.begin(), order.end()));
return 0;
}
send+me+more+money
send+me+money+more
send+more+me+money
send+more+money+me
send+money+me+more
send+money+more+me
me+send+more+money
me+send+money+more
me+more+send+money
me+more+money+send
me+money+send+more
me+money+more+send
more+send+me+money
more+send+money+me
more+me+send+money
more+me+money+send
more+money+send+me
more+money+me+send
money+send+me+more
money+send+more+me
money+me+send+more
money+me+more+send
money+more+send+me
money+more+me+send
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 足し算の項の入れ替え
文字列を文字列のまま扱ってみました。
ただ、デバッグ用初期化と書いてあるところを '\0' から '@' などに変えるとセグメンテーションフォルトを起こしてしまうのですが、そのデバッグは私のほうではできなかったです。
ただ、デバッグ用初期化と書いてあるところを '\0' から '@' などに変えるとセグメンテーションフォルトを起こしてしまうのですが、そのデバッグは私のほうではできなかったです。
#include <stdio.h>
#include <string.h>
#define MAXLEN 32
void imomushi(const char * const res, const char * const rest) {
int start = 0;
int end = 0;
//printf("INFO: res=%s, rest=%s\n", res, rest);
while (1) {
if (strlen(rest) == 0) {
printf("%s\n", res);
return;
}
if (rest[end] == '+' || rest[end] == '\0') {
char buf[MAXLEN+1];
for (int i = 0; i < MAXLEN; i++) buf[i] = '\0'; // デバッグ用初期化
buf[MAXLEN] = '\0';
int i;
strcpy(buf, res);
if (strlen(res) != 0) strcat(buf, "+");
strncat(buf, rest+start, end - start);
i = strlen(buf)+1;
//buf[i] = '\0';
if (start != 0) {
strncpy(buf+i, rest, start - 1);
if (rest[end] == '+')
strcat(buf+i, rest + end);
} else {
if (rest[end] == '+')
strcpy(buf+i, rest + end + 1);
else
buf[i] = '\0';
}
imomushi(buf, buf+strlen(buf)+1);
if (rest[end] == '\0') return;
end++;
start = end;
} else {
end++;
}
}
}
int main() {
imomushi("", "send+me+more+money");
return 0;
}
Re: 足し算の項の入れ替え
王道パターンは、要素をa+b+c+d+eとしたときに、
①[00000],[00001],[00002],[00003],[00004],[00010],[00011],...を作る
②5個の数字が被らないものだけにする
③0~4をa~eに変換して表示
です。
この問題の厄介なところは要素の数だけループしないといけないところです。解決策としては、
・再帰を使う
・スタックを使う(再帰はスタックに変換できるらしいです)
・大きな数字(32bit, 64bit整数など)を除算(/,%)する
・配列をカウントアップしていくルーチンを作る([00000]->[00001]->...[00004]->[00010]->...みたいな感じ)
といったことが思い当たりました。
①[00000],[00001],[00002],[00003],[00004],[00010],[00011],...を作る
②5個の数字が被らないものだけにする
③0~4をa~eに変換して表示
です。
この問題の厄介なところは要素の数だけループしないといけないところです。解決策としては、
・再帰を使う
・スタックを使う(再帰はスタックに変換できるらしいです)
・大きな数字(32bit, 64bit整数など)を除算(/,%)する
・配列をカウントアップしていくルーチンを作る([00000]->[00001]->...[00004]->[00010]->...みたいな感じ)
といったことが思い当たりました。
Re: 足し算の項の入れ替え
とりあえず同じ名称のことは意識せずにやってみた。
Rubyだと2行でできた。\(^O^)/
Rubyだと2行でできた。\(^O^)/
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
プログラムは思ったとおりには動かない。書いたとおりに動く。