[コケ]製作13-1

2803 ワード
CodingTest テキストリンク

1として作成



整数Xには、次の3つの演算があります.
1.Xを3で割って、3で割った.
2.Xを2で割り、2で割ります.
1を減らす.
ある整数N上で上記演算を選択し、1を生成しようとする.演算回数の最小値を使う問題を求めます.
X -> X/3
X -> X/2
X -> X-1
大きな問題->小さな問題の答えを利用する.
  • 点火式定義
  • D[N]=Nが1の最小演算回数である.
  • Xを3で割って3で割った.
  • N -> N/3 -> .... -> 1 => D[N]
  • N/3 -> ... -> 1 => D[N/3]
  • 1 + D[N/3]
  • Xを2で割って2で割った.
  • N -> N/2 -> .... -> 1 => D[N]
  • N/2 -> ... -> 1 => D[N/2]
  • 1 + D[N/2]
  • 1を減算します.
  • N -> N-1 -> ... ->1
  • 1 + D[N-1]
  • D[N] = min(D[N/3]+1 , D[N/2]+1, D[N-1] + 1)

  • N>=2.

  • Nを3を2で割る優先順位で1にする.

  • この方法では正解が得られない.(反例10)
  • は常に最小を求める方法でDynamicで解くとよい.
    重要なのは、小さくなることができるすべての状況を確認することです!!
    • *top-down
  • 再帰関数では、条件の中で最も重要なのは、最小の問題を処理するために条件文が必要であることです.
  • if(n==1) return 0;
  • memoization
  • if(d[n]>0) return d[n];
    • *bottom-up
  • の最小サイズの0に初期化すると、ますます大きな問題で計算され、値が見つかります.
    • 通常top-downは耳にあり、bottom-upは複文で解けます.
    まずbottom-up法で解く.
    import java.util.*;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int d[] = new int[n+1];
		d[0]=1;
		d[0]=1;
		for(int i=2;i<=n;i++) {
			d[i]=d[i-1]+1;
			if(i % 2 ==0)
				d[i]=Math.min(d[i], d[i/2]+1);
			if(i % 3 ==0)
				d[i]=Math.min(d[i], d[i/3]+1);
		}
		System.out.println(d[n]);
	}
}
    うん...トップダウン法で解くとタイムアウトしました.
    import java.util.*;

public class Main {
	static int d[];
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		d = new int[n+1];
		System.out.println(cal(n));
	}
	
	public static int cal(int n) {
		if(n==1) 	return 0;
		if(d[n]>0)	return d[n];
		
		d[n]=cal(n-1) +1;
		
		if(n%3==0) {
			d[n]=Math.min(d[n], cal(n/3)+1);
		}
		if(n%2==0) {
			d[n]=Math.min(d[n], cal(n/2)+1);
		}
		return d[n];
		
	}
}
    理由は、、、数学です.min関数のためです.ほほほ
    import java.util.*;

public class Main {
	public static int d[];
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		d = new int[n+1];
		System.out.println(cal(n));
	}
	
	public static int cal(int n) {
		if(n==1) 	return 0;
		if(d[n]>0)	return d[n];
		
		d[n]=cal(n-1) +1;
		
		if(n%3==0) {
			int tmp=cal(n/3)+1;
			if(d[n]>tmp) {
				d[n]=tmp;
			}
		}
		if(n%2==0) {
			int tmp=cal(n/2)+1;
			if(d[n]>tmp) {
				d[n]=tmp;
			}
		}
		return d[n];
	}
}
    これは崔伯俊先生のコードテストの基礎科目に基づいて書いた文章です.
    [Codility] 9.1 MaxDoubleSliceSum
    百準目覚まし時計(2884)問題を解く