質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.47%

  • C

    3834questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    3626questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

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

解決済

回答 6

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 867

miura_bara

score 18

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

「問題」
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 になります。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • unau

    2016/04/25 17:42

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

    キャンセル

  • 退会済みユーザー

    2016/04/25 18:28

    こちらの質問が他のユーザから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

  • yumetodo

    2016/04/26 00:14

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

    キャンセル

回答 6

+4

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/25 17:52

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

    キャンセル

  • 2016/04/25 18:30

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

    キャンセル

+2

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/25 17:57

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

    キャンセル

  • 2016/04/25 18:23

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

    キャンセル

checkベストアンサー

+1

問題を素直に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;
  }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/26 09:54

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

    キャンセル

  • 2016/04/26 16:51

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

    キャンセル

  • 2016/04/26 21:23

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

    キャンセル

  • 2016/04/28 06:42

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

    キャンセル

  • 2016/04/28 08:22

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

    キャンセル

  • 2016/04/28 10:42

    ヒマだったのでやってみた。ついでに 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;
    }
    }

    キャンセル

  • 2016/04/28 16:54

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

    キャンセル

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/28 03:32

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

    キャンセル

  • 2016/04/28 16:52

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

    キャンセル

0

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

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

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

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

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

  • 蛇足:
     S1, S2 の2つの文字列があたえられたときに、
     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 について、一番長い変換シーケンスを求めるプログラムを書くことは可能でしょうか?
 

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/04/27 00:02

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.47%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C

    3834questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    3626questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。