Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
@Ooriver
Revisions
Report this question
Subscribe question
Help us understand the problem. What is going on with this question?
Q&A
Closed

c言語 再帰関数の問題

Q&A
Closed

大学の問題で、
キーボードから(空白類文字を含むかもしれない)1 行を入力して,先頭の K 文字と最
後の K 文字が順に同じであるかを判定するプログラムを書きたいとする.ただし,K
はマクロで定めなければならず,1 行の長さに上限を勝手に設けてはいけなく,メモリ
を動的に確保してはいけないとする.また,(入力のために打ち込んだ)改行文字を判
定に含めず,2K 文字未満の 1 行が入力された場合は「undecidable」を表示すること.
goto文、繰り返し文も用いらないこと。

といった問題で、正解となるソースコードがわからなく困っています。
こちらの問題は再帰関数について学習している際に出されたので再帰関数を用いて解けるものだと考えています。また、この問題が出されたときにはまだポインタは習っていないので使わないと思います。配列は大丈夫です。

分かる方がいらっしゃいましたら教えていただけると幸いです。

0
2
Answer

その条件だとこんな感じですかね……。

#include <stdio.h>
#define K 3

char data[K+1];

int try(int depth) {
  int ch = getc(stdin);
  if(ch==EOF || ch=='\n') {
    return depth>=K ? 0 : -2;
  }

  int rd = try(depth+1);
  if(rd < 0) return rd;
  if(rd == K) return K;
  return data[K-rd-1] == ch ? rd+1 : -1;
}

int main(void) {
  if(fgets(data, K+1, stdin)==NULL) {
    printf("undecidable\n");
    return 0;
  }

  switch(try(0)) {
  case K: printf("ok\n"); break;
  case -1: printf("ng\n"); break;
  default: printf("undecidable\n");
  }
}

パズル的に面白いのでやってはみましたが、この場合は質問というよりは「かわりにやって欲しいという依頼」になっているので Qiita のコンセプトとしては好ましくないと思います。 何がわからないのか明確にしてください。 何をどこまでやってどこで躓いているのがわからないと意味のある助言ができません。

0
ご返答ありがとうございます。saito様が仰るように確かにこの質問の仕方はqiitaのコンセプトにはずれてしまっていました。次から質問するときはコンセプトに沿った内容にしたいと思います。

一行の長さの制限を定めてはならないということなので、再帰でやってはだめです。スタックオーバーフローが生じます。
私ならまず K 文字分のバッファを二つ用意し、一つをリングバッファにします。getc でそれらを K 文字分埋め、その後はリングバッファのみ更新します。
最終的にリングバッファは入力の最後の K 文字になるので、それをもう一つのバッファと比較し、結果を出力します。

0
Help us understand the problem. What is going on with this answer?
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login