復旦大学研究生気試験テーマ解析(2016-2018)

1.ワークショップ(2018)
1.1集合納入
タイトル:
第1題は、2つの集合を入力して、それぞれその交差と並列集合の中の要素の個数を求めて、各集合の中で同じ要素が存在する可能性があって、最終的な交差と並列集合の中で存在しないべきです.例:入力:4 5 3 4 7 3 4 6 3 2 6出力:2 5
問題を解く:
明らかに問題を送ります.

#include 
#include 
using namespace std;

int main() {
	int M, N;
	cin >> M >> N;
	set A,B,C;
	while (M-- > 0) {
		int temp;
		cin >> temp;
		A.insert(temp);
		C.insert(temp);
	}
	while (N-- > 0) {
		int temp;
		cin >> temp;
		B.insert(temp);
		C.insert(temp);
	}
	int count = 0;
	for (auto iter = A.begin(); iter != A.end(); iter++) {
		if (B.find(*iter)!=B.end()) {
			count++;
		}
	}
	cout << count << " " << C.size() << endl;
	return 0;
}

1.2約数加算
タイトル:
第2題では,1つの数nを入力し,前のn個の数の約数の和を出力する.(イメージには1 sの時間制限があり、ビッグデータセットがタイムアウトする可能性があります.例えば1000000).例えば、入力:7出力:41
問題を解く:
この問題はまず関数を作って与えられた数字の約数和を算出し,大きな循環で加算している.

#include 
#include 
using namespace std;

int countysh(int a) {
	int sum = 1 + a;
	for (int i = 2; i < a; i++) {
		if (a%i == 0)
			sum += i;
	}
	return sum;
}

int main() {
	int input, sum = 1;//1    1;
	cin >> input;
	for (int i = 2; i <= 7; i++) {
		sum += countysh(i);
	}
	cout << sum << endl;
	return 0;
}

1.3交点
タイトル:
第3題、線分の交点を求めて、2組の線分の端点(整型)を入力して、その交点を求めて、交差しないでと無限の交点は1つの話を出力して、交点を出力して小数のを持ちます.
問題を解く:
この問題は少し難しいですが、考えても仕方がないので、doubleに設定して数学の公式y=kx+bで死んだほうがいいです.

#include 
#include 
using namespace std;

int main() {
	double x1, y1, x2, y2, x3, y3, x4, y4;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	double k1 = (y2 - y1) / (x2 - x1), k2 = (y4 - y3) / (x4 - x3), b1 = y1 - k1*x1, b2 = y3 - k2*x3;
	if (k1 == k2)
		cout << "      " << endl;
	else {
		double x = (b2 - b1) / (k1 - k2), y = k1*x + b1;
		cout << x << " " << y << endl;
	}
	return 0;
}

2.コンピュータアカデミー(2018)
2.1衆数を求める
タイトル:
衆を求める衆数は1つのシーケンスで最も多く出現した数である.ユニークでない場合は、小さな値を出力します.最初の代表にはいくつかの数字が与えられます.1<=n<=10^5各数値はint範囲内
サンプル:入力:(最初は数を表す)8 10 3 8 3 2 2
出力:2
問題を解く:
スコアをカードで送る.

#include 
#include 
#include 
using namespace std;

int main() {
	int N;
	cin >> N;
	vector vec;
	while (N-- > 0) {
		int temp;
		cin >> temp;
		vec.push_back(temp);
	}
	sort(vec.begin(), vec.end());
	int max = -1, num = vec[0], constnum = vec[0], count = 1;
	for (int i = 1; i < vec.size(); i++) {
		if (vec[i] == num) {
			count++;
		}else{
			num = vec[i];
			count = 1;
		}
		if (count > max) {
			num = vec[i];
			max = count;
			constnum = num;
		}
	}
	cout << constnum << endl;
	return 0;
}

2.2方程式を解く
タイトル:
1元1次方程式を表す文字列を指定します.解があれば「x＝数字」と出力し、解の個数が無限であれば「infinite solutions」と出力します.解出力「no solution」文字列の長さが256を超えない場合.入力:10 x-2 x-8=4 x+7+x出力:x=5
問題を解く:
この問題は少し難しくて、私の構想は方程式をAx+B=0の形式に簡略化してこの問題を解決することです.ここで、Aは私のコードの中でint xxで、Bは私のコードの中でint xxxです.文字列を読み込んで処理することでxxとxxxを得る.最終出力-xxx/xx、すなわち-B/Aは、最終結果である.

#include 
#include 
#include 
using namespace std;

int main() {
	string str;
	getline(cin, str);
	string num = "";
	int xx = 0;
	int xxx = 0;
	int you = false;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] >= '0'&&str[i] <= '9') {
			num += str[i];
		}
		else if (str[i] == 'x') {
			if (num.empty() || num == "+" || num == "-")
				num += "1";
			stringstream ss;
			ss << num;
			int inum;
			ss >> inum;
			if (you)
				xx -= inum;
			else
				xx += inum;
			num = "";
		}
		else if ((str[i] == '+' || str[i] == '-')&&!num.empty()) {
			stringstream ss;
			ss << num;
			int inum;
			ss >> inum;
			if (you)
				xxx -= inum;
			else
				xxx += inum;
			num = "";
		}
		else if ((str[i] == '+' || str[i] == '-') && num.empty())
			num += str[i];
		else if (str[i] == '='&&!num.empty()) {
			stringstream ss;
			ss << num;
			int inum;
			ss >> inum;
			if (you)
				xxx -= inum;
			else
				xxx += inum;
			num = "";
			you = true;
		}
		else if (str[i] == '=')
			you = true;
	}
	cout << -xxx / xx << endl;
	return 0;
}

2.3骨牌
タイトル:
2*nの床があり、1*2と2*1の骨牌で床を敷く.全部で何種類の状況があるかを聞く.結果は9999983に対して残り、1<=n<=10000であった.入力:6
出力:13
問題を解く:
この問題は法則を見つければいいのですが、dpのタイプの問題(フィボナッチ数列のようなもの)であるべきである.n=1の場合、明らかに1種類のみである.n=2の場合、明らかに後の2種類である.n=3の場合、空間を2つの部分、2*2と2*1に分割することができる.この場合、ちょうどn=1とn=2の場合の総和である....最終的に方程式d[i]=d[i-1]+d[i-2];そしてd[1]=1、d[2]=2;

#include 
using namespace std;

int countnum(int input) {
	if (input == 1)
		return 1;
	else if (input == 2)
		return 2;
	else
		return countnum(input - 1) + countnum(input - 2);
}

int main() {
	int input;
	cin >> input;
	cout << countnum(input) << endl;
	return 0;
}

3.コンピュータ学院(2017)
3.1中位数
タイトル:
整数シーケンスを指定し、中位数を求めます.入力:5 3 2 5 3 7出力:3
問題を解く:
問題にサインして、難しくないです.

#include 
#include 
#include 
using namespace std;

int main() {
	int N;
	cin >> N;
	vector vec;
	while (N-- > 0) {
		int temp;
		cin >> temp;
		vec.push_back(temp);
	}
	sort(vec.begin(), vec.end());
	cout << vec[vec.size() / 2] << endl;
	return 0;
}

3.2検査ビットを求める
タイトル:
9ビット数のISBNを与え、そのチェックビットを求める.ISBN形式は2−02−033598である.チェックビットの計算方法は、各数字を左から右に順に10,9,8,7,6,5,4,3,2に乗じる.Sとは何かを求め,モジュール演算をしてM=S mod 11とする.11-Mが1と9の間にある場合、チェックサムはこの数字である.11-Mが10に等しい場合、検査ビットはXである.11−Mは11に等しく、チェックビットは0である.2−02−033598−0のようなチェックビットを追加したISBNを出力する.入力:2-02-033598出力:2-02-033598-0
問題を解く:
この問題は難易度も感じないので、問題に沿って一歩一歩行けばいいです.

#include 
#include 
using namespace std;

int main() {
	string input;
	cin >> input;
	int multi = 10, sum = 0;
	for (int i = 0; i < input.length(); i++) {
		if (input[i] != '-') {
			int inum = input[i] - '0';
			sum += inum*multi;
			multi--;
		}
	}
	int M = sum % 11;
	M = 11 - M;
	if (M >= 1 && M <= 9)
		cout << input << "-" << M << endl;
	else if (M == 10)
		cout << input << "-X" << endl;
	else if (M == 11)
		cout << input << "-0" << endl;
	return 0;
}

3.3最小生成ツリー
タイトル:
N個の無方向図で、M個のエッジが与えられ、K個の代替エッジから複数のエッジが選択され、図全体が連通し、選択されたエッジ重み値と最小となる.
問題を解く:
これが最小生成ツリーの求め方であり,プリムアルゴリズムやクルースカーアルゴリズムを用いることができるが,ここでは入出力例が与えられず,まずコードを貼らない.
4.コンピュータアカデミー(2016)
4.1最大共通文字列長
タイトル:
2つの文字列を指定し、最大共通サブ列の長さを求めます.入力:fdfdfd 42543 232 fdfdfdjlkj出力:6
問題を解く:
暴力的な解読、2つのサイクル、1つは最初の文字列を遍歴し、もう1つは切り取ったサブ文字列の長さを決定し、stringを呼び出す.find()はinput 2にあるかどうかを見て、あるならば、長さが最も長いかどうかを判断する.

#include 
#include 
using namespace std;

int main() {
	string input1, input2;
	cin >> input1 >> input2;
	int max = -1;
	for (int i = 0; i < input1.length(); i++) {
		for (int j = 1; j < input1.length() - i - 1; j++) {
			int pos = input2.find(input1.substr(i, j));
			if ((pos >= 0)&& j > max) {
				max = j;
			}
		}
	}
	cout << max << endl;
	return 0;
}

4.2接尾辞シーケンス
タイトル:
接尾辞のシーケンスを指定して、値を求めることを要求して、ただ加減します(テーマの説明に基づいて、自分で編んだ例)入力:23+1+出力:6
問題を解く:
この問題はもちろん簡単で、コンパイル原理の四元式変換のようなもので、1つのスタックで解決することができます.

数字に遭遇するとスタックに圧入する.

は、演算子が2つの数a,bをポップアップするたびに遭遇する.演算を行ってスタックに圧入する.

は、表現を遍歴したときにスタック内に1つの要素しかないかどうかを判断し、ある場合は最後の結果とする.複数の要素の説明式にエラーがあります.

#include 
#include 
#include 
using namespace std;

int main() {
	string line;
	cin >> line;
	stack sta;
	for (int i = 0; i < line.length(); i++) {
		if (line[i] >= '0'&&line[i] <= '9')
			sta.push(line[i] - '0');
		else if (line[i] == '+') {
			int a = sta.top(); sta.pop();
			int b = sta.top(); sta.pop();
			sta.push(a + b);
		}
		else if (line[i] == '-') {
			int a = sta.top(); sta.pop();
			int b = sta.top(); sta.pop();
			sta.push(a - b);
		}
	}
	if (sta.size() == 1) {
		cout << sta.top() << endl;
	}
	else
		cout << "      " << endl;
	return 0;
}

4.3ハフマン符号化
タイトル:
文字列を指定して、ハフマン符号化の最短長を求めます.入力:aaaabbbbccdde出力:33
問題を解く:
このテーマは難しいですが、まずmapで各文字が現れる頻度を格納し、すべての文字の頻度をvecterに変換してvecと名付けました.このとき問題は,ハフマン符号化のWSLをどのように求めるかというデータのセットを得ることに転化する.だから私は新しい関数huffman()を構築しました.同時にハフマンツリーを構築するために、ツリーのノードを格納するためにノードを追加しました.ハフマンツリーがツリーを構築するプロセスは下から上であり、検索のプロセスも下から上であるため、私たちのノードにはparentが親ノードを指す必要があります.最後にWSLを計算するために、ノードがリーフノードであるかどうかを示すleafの変数も必要です.huffman()関数ではvec 1は、まだツリーを構築するために使用されていないノードを表し、vec 2は、ツリーを構築するために使用されたノードを表すために使用されます.私たちはvec 1から2つの重み値が最も小さいノードをポップアップし、2つの最小ノードの親ノードとして新しいノードを作成します.新しく作成したノードをvec 1に、すでにツリーとして使用されているノードをvec 2に入れます.vec 1にノードが1つしか残っていない、すなわち最後のルートノードまで.最後にvec 2のノードを遍歴し、葉ノードに遭遇したとき、絶えず循環し、経路長を得る.このようにして,最後のWSLを算出する.

#include