読者です 読者をやめる 読者になる 読者になる

seri::diary

プログラミングのこととかポエムとか

修正)コーディングテスト 例題を解いてみた

コーディングテスト

前回のブログにてcgios technologiesの採用試験の過去問を再帰処理で解いてみたが、
以下のような課題が生じた。

最初はもうちょいシンプルに書いていたのだが
1文字目を指定して、その次に続く文字列を指定して再起呼び出しすると
何故か同じパターンが4つ表示されるという現象が発生した。


上記課題の原因が分かったので
修正版コードを再度掲載する。

<?php
set_time_limit(120);

class joinCharClass{
    
    public $joinedCharStack = "";
    public $count = 0;
    
    public function __construct($joinedCharStack){
        $this->joinedCharStack = $joinedCharStack;
    }
    
    public function printStrings($joinedChar){

        if($this->joinedCharStack !== $joinedChar){
            $this->joinedCharStack = $joinedChar;
            echo $this->joinedCharStack . " \n";
            $this->count++;
            return;
        }else{
            return;
        }
    }

   
    public function joinChar($n, $char, $joinedChar ){

/* 修正部分
*

        if($n == 0){
            $this->printStrings($joinedChar);
            return;
        }
        
        $joinedChar .= $char;
        --$n;
        
       $this->joinChar($n, "A" ,$joinedChar);
       $this->joinChar($n, "C" ,$joinedChar);
       $this->joinChar($n, "G" ,$joinedChar);
       $this->joinChar($n, "T" ,$joinedChar);
*/

//修正後
        if($n == 1){
            echo $joinedChar . $char . "<br>\n";
            return;
        }
      
       $this->joinChar($n-1, "A" ,$joinedChar . $char);
       $this->joinChar($n-1, "C" ,$joinedChar . $char);
       $this->joinChar($n-1, "G" ,$joinedChar . $char);
       $this->joinChar($n-1, "T" ,$joinedChar . $char);  


    }
}


//test
$jS = new joinCharClass("");

$jS->joinChar(5, "A", "");
$jS->joinChar(5, "C", "");
$jS->joinChar(5, "G", "");
$jS->joinChar(5, "T", "");


?>


実際にjoinChar内で何の引数が渡されて
再帰処理されるかを考えてみると意外と原因はあっさりしていた。

簡単に書くと、joinChar(2 , "A" "")で呼び出してn=0になった時に、

  1. n = 0で結合した文字列がechoされる → AA
  2. returnで呼び出し元に戻る
  3. 戻った先で次の再帰呼び出しされる →joinChar(0, "C" , "AA")
  4. n = 0で結合した文字列がechoされる → AA
  5. returnで呼び出し元に戻る
  6. 戻った先で次の再起呼び出しされる →joinChar(0, "G" , "AA")

という感じで、まぁ根本的に再帰呼び出し
スタックで管理されているの忘れてたというか
どういうものかを忘れていたのが原因と考えられるバグ・・・

いやはや、たまにはこういうコードも書いて
常に基礎的なコーディング力を鍛え続けなければならないと痛感した。

これでも買ってやってみようかな

プログラミングコンテストチャレンジブック

プログラミングコンテストチャレンジブック