HNUCM 2018級「アルゴリズム分析と設計」練習二題解

HNUCM 2018級「アルゴリズム分析と設計」練習二題解
前言:再帰テーマ:1、再帰終了条件を探す2、再帰方程式を探す
A:判定素数
直接に数を与えて、素数かどうかを判断してください.
标题:まったくの大水問題...
B:対称行列
題意:n次元マトリクス、対称マトリクスかどうかを判断する
标题:何も言わないで、a[i][j]=a[j][i]と判断すればいい
C:行列対角求和
題意:nは行列で、その主対角線とその副対角線の和を求めます
问题解:この问题はまったく穴があいていないので、long longさえ穴をあけていない.
直接和を求めればよい:主対角線:i=j副対角線:i+j=n-1(0で始まる)
D:文字統計
題意:文字列を与え、大文字、小文字、アラビア数字、スペースの個数を判断する
直接遍歴すればいい
E:再帰求和
题意:再帰で、以下の数列の前のn项を求めます:s=1-1/2+1/3-1/4+1/5-1/6+...
标题:再帰終了条件を見つける

if(n==1)
	return 1;
else
	return f(n-1)+1.0/n;

F:フィボナッチ数
題意:複数組の入力、各組の入力は与えられたn番目のフィポラチッチ数を求める(最後の6ビットしか出力しない)
问题解:この问题は暴力で再帰すると、必ずtle(タイムアウト)になるので、配列で保存して、スペースで时间を変えなければなりません
G:蜂の巣
标题:蜂の巣を歩く;複数組のデータ、与えられた起点と終点、何種類の歩き方があることを求めます
問題:

if(n==1)
	return 1;
else if(n==2)
	return 2;
else
	return f(n-1)+f(n-2);

H:数字加算
題意:正の整数nを与えて、その各桁数の和を求める
问题解:再帰を学んで、再帰で书いて、直接个の位からずっと前へ押すことができて、再帰の终わりの条件を探し当てます:nただ1桁の数だけ残った时

if(n/10==0)
	return n;
else
	return f(n/10)+n%10;

I:ウサギを飼う
标题:ある人は1匹のウサギを養子にして、成熟期は1日で、n日目にどれだけのウサギがあることを求めます
問題解:同じように再帰的な終了条件を探します.

if(n==1)
	return 1;
else
	return f(n-1)*2;

J:XPの階段
标题:xpは階段を跳んで、一度に1段、一度に2段、一度に3段跳ぶことができます.第n級にジャンプして何種類の方案がありますかを聞きます
問題解:xpの開始位置が第1級であることに注意して、そこで再帰の終了条件と再帰方程式を探します

if(n==1)
	return 1;
else if(n==2)
	return 1;
else if(n==3)
	return 2;
else
	return f(n-1)+f(n-2)+f(n-3);