11. 비둘기 집 원칙이란 함수 f가 n개의 서로 다른 입력에 대해 n개 보다 작은 서로 다른 출력이 나온다면
a ≠ b이고 f(a) = f(b)인 두 개의 입력 a, b가 존재한다는 것이다. 이와 같이 입력 값이 서로 다르면서 함수 값이 같은 a, b를 찾는 C++프로그램을 작성하라. 입력은 1, 2, ..., n을 가정한다.
#include <iostream>
using namespace std;
void Search(int* y, int n);
int main() {
int x[11] = { 0,1,2,3,4,5,6,7,8,9,10 }; //0~10까지의 입력표
int y[12] = {}; // 12개 입력하면 적어도 2개의 값이 0~10사이에서 같음
for (int i = 0; i < 12; i++) {
cout << i + 1 << "번째 숫자를 입력하세요(범위: 0 ~ 10) : ";
cin >> y[i];
}
cout << "입력된 1번 ~ 12번째 숫자 배열 : ";
for (int i = 0; i < 12; i++) {
cout << y[i] << " ";
}
cout << endl;
Search(y, 12);
}
void Search(int* y, int n) {
int a, b; //입력값이 같은 두 값의 입력 순서
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (y[i] == y[j]) {
a = i + 1;
b = j + 1;
cout << a << "번째 입력 값과 " << b << "번째 입력 값이 " << y[i] << "로 같습니다." << endl;
}
}
}
}
// 결과
- 문제 이해를 위해 비둘기집 원리 예제를 활용하여 문제를 푼 버전도 추가.
//비둘기집 원칙을 활용한 예제를 떠올려서 문제 풀었음
// 0점에서 10점까지 1점 단위로 채점되는 시험에서 학생이 12명 있으면 적어도 2명의 학생의 점수가 같음
// 이때 같은 점수인 학생 a, b를 찾아라. (a, b는 학생의 번호인 것으로 간주)
#include <iostream>
using namespace std;
//0점에서 10점까지 1점 단위로 채점되는 기말시험에서 학생 12명이 있으면
//적어도 2명의 학생이 같은 점수가 된다.
//같은 점수인 학생 a, b를 찾아라. (a, b는 학생의 번호인 것으로 간주)
void Search(int *student, int n);
int main() {
int grade[11] = { 0,1,2,3,4,5,6,7,8,9,10 }; //표준 점수표
int student[12] = {}; //1번부터 12번 학생의 점수 배열
for (int i = 0; i < 12; i++) {
cout << i + 1 << "번 학생 점수를 입력하세요(점수는 0점 ~ 10점) : ";
cin >> student[i];
}
cout << "1번 ~ 12번 학생의 점수표 : ";
for (int i = 0; i < 12; i++) {
cout << student[i] << " ";
}
cout << endl;
Search(student, 12);
}
void Search(int *student, int n) { //n=학생 수
int a, b; //점수가 같은 두 학생의 번호
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (student[i] == student[j]) {
a = i+1;
b = j+1;
cout << a << "번 학생과 " << b << "번 학생의 점수가 " << student[i] << "점으로 같습니다." << endl;
// if문 안에 출력을 넣어서 점수가 같은 두 학생을 모두 찾도록 함.
// 1번 2번의 점수가 같고, 3번 4번 학생의 점수가 같으면 둘 다 출력됨.
}
}
}
}
*나중에 2회독때 https://dokhakdubini.tistory.com/188님 풀이도 공부해보기
12. 어떤 양의 정수 n에 대해 n이 자신의 모든 제수들의 합인지를 알아 내는 C++ 프로그램을 작성하라.
즉, 1 ≤ t < n이고 n의 제수가 되는 모든 t의 합이 n인지 검사하는 것이다.
#include <iostream>
using namespace std;
int Divisors(int n);
int main() {
int n;
cout << "정수 n을 입력하세요 : ";
cin >> n;
if(n==Divisors(n))
cout << "n의 제수가 되는 모든 값들의 합이 " << Divisors(n) << "이므로 n이 자신의 모든 제수들의 합이다." << endl;
else
cout << "n의 제수가 되는 모든 값들의 합이 " << Divisors(n) << "이므로 n이 자신의 모든 제수들의 합이 아니다." << endl;
}
int Divisors(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
if (n % i == 0)
sum += i;
}
return sum;
}
*정수 n에 대해 n이 자신의 모든 제수들의 합인지 = n의 약수(n 제외)를 다 더하면 n이 되는지
*Divisors함수 안에 반복문은 n의 약수 구하여 sum에 더하는 것
13. 함수 F(x)를 다음과 같이 정의한다.
if (x가 짝수) F=x/2;
else F=F(F(3x+1));
F(x)는 모든 정수 x에 대해 완료한다는 것을 증명하라.
[힌트 : (2i + 1)2^k-1 형태의 정수를 가정하고 귀납법을 사용하라.]
2(i+1)2^k -1일 때와 (2(i+1)+1)2^k - 1일 때 모두 성립하므로 수학적 귀납적으로 증명됨.
14. S가 n개의 원소로 이루어진 집합일 때 S의 멱집합(powerset)은 S의 모든 가능한 부분 집합이다.
즉 S = (a, b, c)이면 powerset(S) = { (), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)} 이다. powerset(S)를 구하는 순환 함수를 작성하라.
#include <iostream>
using namespace std;
char Data[4] = { 'a','b','c','d' };
int n = sizeof(Data) / sizeof(Data[0]);
bool include[4];
void Powerset(int k);
int main() {
Powerset(0);
}
void Powerset(int k)
{
if (k == n)
{
cout << "{ ";
for (int i = 0; i < n; i++)
{
if (include[i])
cout << Data[i] << " ";
}
cout << "}" << endl;
return;
}
//data[k]를 포함하지 않는 경우
include[k] = false;
Powerset(k + 1);
//data[k]를 포함하는 경우
include[k] = true;
Powerset(k + 1);
}
- 출력 결과
- 코드 해석
*다시 풀 때 참고 하시오
참고:https://devsnote.com/asks/2248, https://www.youtube.com/watch?v=nkeMRRIVW9s&t=184s
15. [하노이 탑] 세 개의 탑이 있고 첫 번째 탑에는 반경이 서로 다른 64개의 원반들이 쌓여 있다. 각 원반은 반경이 큰 순서로 아래부터 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 탑에서 세 번째 탑으로 원반을 옮기려 한다:
(a) 한 번에 한 개의 원반 만을 다른 탑으로 옮길 수 있다.
(b) 쌓아 놓은 원반은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 순환 함수를 만들라.
#include <iostream>
using namespace std;
void Hanoi(int n, char start, char end, char sub);
int main() {
int n;
cout << "원판의 개수를 입력하세요 : ";
cin >> n;
int start = 'A';
int end = 'C';
int sub = 'B';
Hanoi(n, start, end, sub);
}
void Hanoi(int n, char start, char end, char sub) {
if (n == 1)
cout << n << "번 원판을 " << start << "에서 " << end << "로 이동" << endl;
else {
Hanoi(n-1, start, sub, end);
cout << n << "번 원판을 " << start << "에서 " << end << "로 이동" << endl;
Hanoi(n - 1, sub, end, start);
}
}
//코드 해석
* 참고 : https://mgyo.tistory.com/185