━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ データ構造・アルゴリズム論 チャレンジ問題 (文字列の辞書順列挙) ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
●報告内容 以下の問題への答案のファイル(プログラムファイルと報告ファイル)を作り， 1月17日(金)の14:40までに Moodle で提出する． 答案の内容に応じて，最大で期末試験10点分の加点評価がなされる． プログラムや実行結果が単に羅列されたものより，丁寧な解説や考察のあるものが 高く評価される． ●問題 (1) 入力として二つの非負整数 m と n が与えられたときに，英文字 a〜z のうちの 始めの m 文字から(文字の重複を許して)最大で n 個を，(文字列の重複を許さず) 辞書順にすべて列挙するプログラムを作れ．入力はコマンドライン引き数から受け取り， 結果は標準出力に書き出すこと．たとえば，入力 m＝3，n＝2 に対して 次の13個の文字列を出力できればよい．先頭の空文字列に注意すること． ---------------------------------------------------------------------- a aa ab ac b ba bb bc c ca cb cc ---------------------------------------------------------------------- (2) 作成したプログラムのアルゴリズムとその動作を，小さな m, n (2〜4程度)の 実行結果を使って解説せよ． (3) 講義で学んだ(あるいは独学した)データ構造やアルゴリズム設計技法が， 作成したプログラムでどのように使われているかを，使用理由と共に述べよ． (4) 作成したプログラムの時間計算量について考察し，m＝5 の場合の 小さな n (0〜11程度) での実行時間に基づいて，m＝5, n＝15 の場合の 実行時間を推測(または実測)せよ．計算量の解析が難しいなら， 文字列の総数の変化に基づいて考察してもよい． (5) 余力があれば，データ構造やアルゴリズムを変えたプログラムを作り， 実行時間や記憶量の観点での得失を論じよ． ●提出要領 問題(1)の答案は strings.c (拡張子は適宜変更，他のファイルも必要なら追加) というプログラムファイルに書き，問題(2)〜(5)の答案は report.pdf という 報告ファイルに書く．各ファイルの冒頭には学籍番号と氏名を書くこと． プログラミング言語には paiza.IO 上で動作するものを使える． プログラムには，適度に注釈を入れて読みやすくする．また，報告でプログラムや 実行結果を引用して説明する際には，どの部分の説明か分かりやすいように， 行番号や記号等の目印を付ける． 基礎知識の文献調査や，他人との意見交換を推奨するが，プログラムや報告は 自らの理解に基づいて自作する．他人の文書(または生成AI等の出力)を 参考にした場合には，ファイル中に出典(本の情報やウェブページのアドレス等)を 明示すること．また，他人と相談して答案を作った場合にも， 誰とどの部分について相談し，自分で考えた(作った)部分がどこかを明記すること． 出典を示さずに他人の文書を転載(流用)した報告は，0点と評価される． ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 授業のホームページ 山田 俊行 https://www.cs.info.mie-u.ac.jp/~toshi/