ガジェット通信 GetNews

見たことのないものを見に行こう
「ジャスティス・リーグ」特集サイト

第120回「今週のアルゴリズム:ソートされないカード」正解者発表

DATE:
  • ガジェット通信 GetNewsを≫

「今週のアルゴリズム」とは

「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。

第120回は「今週のアルゴリズム:ソートされないカード」の問題です。

問題文「第120回 今週のお題:ソートされないカード」

1~n までの整数が1つずつ書かれている n 枚のカードを横一列に並べます。
カードを左から順に一枚ずつ見て、書かれている数字が i なら、左から i 番目のカードと交換する、という作業を右端のカードまで繰り返します。

例えば、3, 2, 5, 4, 1の順に並んでいると、最初のカードは 3 なので3番目のカードである 5 と交換し、5, 2, 3, 4, 1となります。
次のカードは 2 なので2番目のカードと交換(交換は発生しない)、その次のカードは 3 なので3番目のカードと交換(交換は発生しない)、その次のカードは 4 なので4番目のカードと交換(交換は発生しない)、その次のカードは 1 なので1番目のカードである 5 と交換し、1, 2, 3, 4, 5となり、昇順に並べ替えられます。
※カードは常に左から順番に見ていきます

右端まで処理した結果、書かれている数字が昇順に並ばない初期配置が何通りあるかを求めます。

標準入力から n が与えられるとき、書かれている数字が昇順に並ばない初期配置が何通りあるかを求め、標準出力に出力してください。
例えば、n = 4 のとき、24通り中、以下の3通りがありますので、サンプルのように出力します。

2, 3, 4, 1
3, 4, 2, 1
4, 3, 1, 2
(n は最大で8とします。余裕がある人は、もう少し大きな n についても考えてみてください)

【入出力サンプル】
標準入力
4

標準出力
3

正解者

おめでとうございます!正解者のみなさんです。(新着順)

strauss様
Tiz様
angel様
a992571様 

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。