2021-11-23
復帰する
再帰関数について議論しましょう.

第1期10872工場

https://www.acmicpc.net/problem/10872

質問する

0以上の整数Nが与えられる.このときN!出力するプログラムを作成してください.

入力

第1行は整数N(0≦N≦12)を与える.

しゅつりょく

1行目N!出力します.

Java 11

import java.util.*;
public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      int N;
      N = sc.nextInt();

      System.out.println(factorial(N));
   }
   
   public static int factorial(int N) {
      if(N<=1) {
         return 1;
      } else {
         return N*factorial(N-1);
      }
   }
}

第2期10870フィボナッチ数5

https://www.acmicpc.net/problem/10870

質問する

フィボナッチ数は0と1で始まる.0番目のフィボナッチ数は0で、1番目のフィボナッチ数は1です.2番目から前の2つのフィボナッチ数の和です.
このようにしてFn=Fn−1+Fn−2(n≧2)となる.
n=17までは、次のようにフィボナッチ数を用いる.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
nが与えられると,n次フィボナッチ数を求めるプログラムを記述する.

入力

最初の行はnです.nは20以下の自然数または0である.

しゅつりょく

1行目はn番目のフィボナッチ数を出力する.

Java 11

import java.util.*;
public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
 
      int n;
      n = sc.nextInt();
 
      System.out.println(fibonacci(n));
 
   }
 
   static int fibonacci(int n) {
      if (n == 0)
         return 0;
      if (n == 1)
         return 1;
      return fibonacci(n-1) + fibonacci(n-2);
   }
}

3次2447星図-10

https://www.acmicpc.net/problem/2447

質問する

再帰的なパターンで星を撮りましょう.Nは3の累加二乗(3,9,27.)である.表示、大きさNのパターンはN×n正方形形状.
大きさ3のパターンは真ん中にスペースがあり、真ん中のすべての格子を除いて星のパターンがあります.
nが3より大きい場合、nサイズのパターンはスペースで塗りつぶされます(N/3).×(N/3)N/3の大きさのパターンで囲まれた正方形.例えば、サイズ27のパターンは、サンプル出力1と同じである.

入力

1行目はNです.Nは3の三次方です.すなわち、ある整数kに対して、N=3 kであり、このとき1≦k<8である.

しゅつりょく

1行目からN行目まで星を出力します.

Java 11

import java.util.*;
public class Main {
   static char[][] array;
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      int N;
      N = sc.nextInt();
      
      array = new char[N][N];
      
      star(0, 0, N, false);
      
      StringBuilder sb = new StringBuilder();
      for(int i=0; i<N; i++) {
         for(int j=0; j<N; j++) {
            sb.append(array[i][j]);
         }
         sb.append('\n');
      }
      System.out.print(sb);
      }
   
   static void star(int x, int y, int N, boolean blank) {
      
      // 공백칸일 경우
      if(blank) {
         for(int i=x; i<x+N; i++) {
            for(int j=y; j<y+N; j++) {
               array[i][j] = ' ';
            }
         }
         return;
      }
      
      // 더이상 쪼갤 수 없는 블록일 때
      if (N == 1) {
         array[x][y] = '*';
         return;
      }
      int size = N/3;
      int count = 0;
      for (int i=x; i<x+N; i+= size) {
         for (int j=y; j<y+N; j+= size) {
            count++;
            if (count == 5) {
               star(i, j, size, true);
            } else {
               star(i, j, size, false);
            }
         }
      }
   }
}

4階11729ハノイタワー移動順

https://www.acmicpc.net/problem/11729

質問する

3本の棒があり、1本目の棒にはn個の半径の異なる円板が積み上げられている.各円板は半径の大きい順に積み上げられている.現在、修道僧たちは以下の規則に従って、最初の棒から3番目の棒に移動します.
一度に1枚の原版を別の塔に移すしかない.
積み上げられたフィルムはいつも上のほうが下のより小さい.
プログラムを作成し、この操作を実行するために必要な移動順序を出力します.ただし、移動回数を最小限に抑える必要があります.
下図は5枚のバックグラウンドの例です.

入力

第1行は、第1の棒に積まれた円板の個数N(1≦N≦20)を与える.

しゅつりょく

1行目に移動した回数出力K.
2行目から実行プロセスの出力を開始します.2行目から、2つの整数A BをK行に分けて出力します.これは、A番タワーの一番上の円板をB番タワーの一番上に移動することを意味します.

Java 11

import java.util.*;
public class Main {
   public static StringBuilder sb = new StringBuilder();
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      int N;
      N = sc.nextInt();
      
      sb.append((int) (Math.pow(2, N) - 1)).append('\n');
      
      Hanoi(N, 1, 2, 3);
      System.out.println(sb);
   }
   
   // N:원판의 개수, start:출발지, mid:옮기기 위해 이동해야할 장소, to:목적지
   public static void Hanoi(int N, int start, int mid, int to) {
      
      // 이동할 원판의 수가 1개
      if(N==1) {
         sb.append(start + " " + to + "\n");
         return;
      }
      
      // N-1개를 A에서 B로 이동
      Hanoi(N-1, start, to, mid);
      
      // 1개를 A에서 C로 이동
      sb.append(start + " " + to + "\n");
      
      // N-1개를 B에서 C로 이동
      Hanoi(N-1, mid, start, to);
   }
}