N の文字列を指定回数処理する

Question

プログラミングの学習で詰まってしまいました。アルゴリズムだけでもわかる方いらっしゃらないでしょうか。

「問題」
1 から N までの数字からなる長さ N の文字列 S が与えられます。 あなたは、この文字列に対し以下の操作を M 回繰り返します。

S の 1 文字目を取り除く。書かれている数が A とすると、A 番目にその数字を挿入する。
例えば、文字列 36452412 に対してこの操作を行うと 64352412 となります。 S に M 回操作を行って得られる文字列を出力してください。

制約
1≤|S|≤9
S は 1 から |S| までの数字からなる
0≤M≤1018

入力例
36452412
1
出力例
64352412

//36452412 に対して一回操作を行うと 64352412 になります。

Comments

[unau]

アルゴリズムはすでに問題文で書かれています。
自分がわかるところまで、試したところまでのコードを示してください。

[yumetodo]

そもそもCなのかC++なのか、CだとしてC89なのかC99以降なのか、C++だとしてC++98なのかC++03なのかC++11以降なのか、それが問題だ

Answer 1

アルゴリズムは記載のとおりでしょ。
「文字列 S」を用意する。
「S の 1 文字目を取り除く。書かれている数が A とすると、A 番目にその数字を挿入する。」
「 S に M 回操作」を行う。

Comments

[miura_bara]

プログラミング初心者のためアルゴリズムのイメージはつきましたがどうプログラムで表現したらようかで悩んでしまいます。できれば教えていただきたいです...

[退会済みユーザー]

悩んでないで、書いてみればいいと思うよ。
その後で再度不明箇所を相談すれば良い。

Answer 2

操作の方法は書いてあるからそのままコードに落としこむだけでしょう。
何がわからないのでしょう？
処理の方法でしょうか？
それならN桁の数字を「N桁の数」として処理するのはなく各桁を全部1桁の数としてバラして処理すればいいのでは？
6桁なら6個のint型の配列を用意して全部バラして配列に入れたら後は入れ替えだけになります。

Comments

[miura_bara]

コードに落とし込む過程でどう表現していいか全くわかりません。。。
プログラムの例があれば教えていただきたいです。

[PineMatsu]

C/C++をどこまで勉強してるんでしょうか？基本的な文法や構文、標準関数など基礎的な知識がないと、単に回答を示すだけになってしまい、それはmiura_baraさんにとってもいいことではないと思います。
プログラムの流れや考え方を論理的に説明できなければプログラムは組むことができません。数学の問題を解くのと同じです。数学の場合は数式で表現しますが、プログラムの場合はC言語ならC言語の文法で表現するわけです。その表現が未だできないのなら、問題を解くのは表現できるようなってからです。表現できるというのは意味を理解しているということと同じです。
厳しく聞こえるかもしれませんが、プログラマになりたいのならそういう基礎を身につけないとなれませんよ。ネットからコピペだけで済むような甘い世界ではない。

Answer 3

問題を素直にC++に落とし込むとこうなりますかね。

#include <iostream>
#include <deque>

int main() {
  using namespace std;
  deque<int> S = { 3, 6, 4, 5, 2, 4, 1, 2 };
  const int M = 3; // 以下の処理をM回くりかえす
  for ( int i = 0; i < M; ++i ) {
    int A = S.front();        // 先頭文字をAとする
    S.pop_front();            // 先頭文字を取り除く
    S.insert(S.begin()+A, A); // SのA番目にAを挿入する
    cout << i+1 << " : ";
    for ( int n : S ) cout << n; cout << endl;
  }
}

Comments

[episteme]

これがベストアンサー?
あなたは"勉強したい"んじゃなかったの?

[PineMatsu]

私も含めて他の人は考え方だけ書いてコードを書かなかったからでしょう。スレ主さんはもう一つ別の質問を投稿してましたけど、そちらでもどなたかがコードを書いたらそれをベストアンサーにしてましたからね。
epistemeさんのコードはdequeを使ってますけど、スレ主さんはdequeとかのコンテナを習ってるのかな？コンテナ習うぐらいだったらこれくらい書けるはず。
習ってないのにこのコードを先生に提出したら、誰かに回答を聞いたか、C++に習熟している、のどっちらかだと思われるはず。（たぶん前者）
まあ、知ったことではないんですがね。

[episteme]

うん、僕もそう踏んでコードを示しました。
「ややこしそうなことがさっくり実装できる」好例でしょうから、
いい勉強になればいいな、と。

[katoy]

//36452412 に対して一回操作を行うと　64352412　になります
と質問文にありますが、
このプログラムを実行すると
64532412 と出力されます。(3 番目の数字が異なっている)
これはどちらが正しいのでしょうか？

[episteme]

挿入位置が取り除く前/後のどっちなのかによりますか。
問題文には 「先頭を取り除く/それがAならA番目に挿入する」とあったので
取り除いた後と解釈しました。
削除前ならA番目に挿入ののち、頭を切ればよろしいな。

[episteme]

ヒマだったのでやってみた。ついでに string化。

#include <iostream>
#include <string>

int main() {
using namespace std;
string S = "36452412";
const int M = 3;
for ( int i = 0; i < M; ++i ) {
char A = S.front(); // 先頭文字をAとする
S.insert(S.begin()+(A-'0'), A); // SのA番目にAを挿入する
S.erase(0,1); // 先頭文字を取り除く
cout << i+1 << " : " << S << endl;
}
}

[PineMatsu]

「ありがとうございました」の一言もなしに、投稿者は姿を表さなくなりましたね。
礼儀もなってないし、本当にプログラマを目指してるのか疑問。

Answer 4

「S の 1 文字目を取り除く。書かれている数が A とすると、A 番目にその数字を挿入する。」
配列で考えた場合・・・
１．S の 1 文字目を取り除く→先頭の文字Aを取り出す。Aを数値に変換してその分前詰めする。
２．A 番目にその数字を挿入する→１で空いた場所にAを入れる。
1と2をM回行う。
注）配列は０から始まる事を忘れないように・・・

Comments

[cateye]

プログラミングは、問題（仕様）をプログラムにする技術です。誰かが作った処理をコードに落とすことではありません（コピペなんて論外です）　 epistemeさんのコードをすべて説明できますか？・・・でなければ、勉強にはなっていません。

[PineMatsu]

投稿者のコメントがベストアンサーを選んでから無いですねぇ。しかも、「ありがとうございました」の一言もなし。
ここは宿題の回答をしてもらうところではないと思うんですが。
プログラマを目指す学生かなと思ってみんな教育的な意味で色々とアドバイスしているのに。

Answer 5

あなたがいつもどうやってプログラミングしているかわかりませんが、まずはプログラミングをする前に紙に流れを書きましょう。コードじゃなくて文章でです。
そうするとだんだんコードが見えてきますよ。

できなくてもいいので、コードを書いてください。プログラミングはやって覚えるしか方法はありません。

Answer 6

... S に M 回操作を行って得られる文字列を...

この問題の本当の狙いは、手続きをコードに落とすことではなくて、
なんらかの法則性をみつけて、それを利用して効率よく変換結果の文字列を求めることなのではないでしうか？

1000億回の操作をおこなった結果を求めるとしたら、機械なら文句を言わずに1000億回の操作をするでしょう。
でも、人間なら、何回か操作したら、繰り返しが現れることに気が付くはずです。
仮に10 回目で最初の文字列にもどったとしたら、1000 億回の操作の文字列は最初の文字と同じだと即答できます。(1000 億は 10 の倍数だから)

特に この問題の操作では, 先頭の文字が 1 の場合は操作しても変化が起こらないので、 即答できますね。

• 質問文について疑問があります。

.... 1 から N までの数字からなる長さ N の文字列 ...
とかかれているのに、サンプルは 36452412 です。これは 1..6 からなる長さ 8 の文字列です。
問題文が間違っているのか、サンプルが不適切なのか どちらなのでしょう。

• 蛇足：

S1, S2 の２つの文字列があたえられたときに、
S1 に何回の操作をしたら S2 になるか、あるいは何回操作しても S2 にならないかをなるべく速く判定するプログラムを書くことは可能でしょうか？

追記： 2016-04-27
N = 3 の場合の文字列の変化は次パターンがあります。
(操作をしても変化をしなくなる部分は *xxx のように書いています)
[*123]
[*132]
[213, *123]
[321, 213, *123]
[312, *123]
つまり、M >= 3 なら　S の値によらず、結果は常に 123 となります。
また、 213 -> 132 へ変換されることは無いということです。
N = 3 の場合、一番長い変換シーケンスは [321, 213, *123] です。
他の N について、一番長い変換シーケンスを求めるプログラムを書くことは可能でしょうか？

Comments

[cateye]

>何回操作しても S2 にならない
まず思いつくのは、長さが違う場合、S1とS2に含まれている文字が違う（どちらにしかない文字がある）、あるいは個数が違う場合は同じ文字列にはなりません・・・ここまではOnで解けますね。・・・あとは××？