今日は木曜日なので６時からサークル。
普段通り問題を解きました。
今日の問題は
与えられた分数を単位分数（分子が１、分母が正整数の分数）に分解していくとき、何通りの分け方があるかという問題。
入力はｐ／ｑに当たる ｐとｑ、単位分数の分母の積の限界値ａ、分割の限界数ｎが
ｐ ｑ ａ ｎ
で与えられ、最後は
０ ０ ０ ０
で示される。
制約
ｐとｑ＜＝８００、ａ＜＝１２０００、ｎ＜＝７
＊ ＊ ＊ ＊ ＊
import java.util.Scanner;
class UFP {
static int count,a,n;
static void ufp(int p,int q,int k,int m,int d){
if(n<m||a<k||p*d-q<0){
return;
}else if(p*d-q==0){
count++;
return;
}else{
for(int i=d;i<=a/k;i++) ufp(p*d-q,q*d,k*i,m+1,i);
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int p,q;
while(true){
count=0;
p=scan.nextInt();
q=scan.nextInt();
a=scan.nextInt();
n=scan.nextInt();
if(p==0&&q==0&&a==0&&n==0){
break;
}else{
for(int i=1;i<=a;i++){
ufp(p,q,i,1,i);
}
System.out.println(count);
}
}
}
}
＊ ＊ ＊ ＊ ＊
一応今日活動内で書いたやつ。Acceptedはもらえました。
とりあえず分母２の単位分数から順番に分母を大きくして引いていく感じ。
引いて０以下になったり、分割した回数がｎより多くなったらその地点で呼び出し元に戻ります。
ただ通分していったとき約分の作業を計算時間の短縮のためカットしたのでオーバーフローが心配。
初めは最大公約数求めて割る（要するに約分）という作業を入れていたが計算時間が増えるのでカット。
結局時間が無かったのでそこまでは確認しなかった。
それとほかにも短縮できるところがありそうです。
そのあとは今日来た部員全員で晩御飯。
量が毎回俺にとっては非常に多いですがおいしかったです。みんなでたべるからというのもあるでしょうが。
にしても最近プログラミングの本の中身が非常に読みづらい。
やっぱり後悔する前にカーティス大佐に分からないところを聞きに行こうかな……。