접속에 성공하셨군요! 축하합니다.
아래의 프로그램을 분석하고, 틀린 부분을 찾으시오!
먼저, 순환알고리즘을 이용한 프로그램이고, 수학을 이용한 프로그램입니다.
그리고 마지막으로 동적표를 이용한 프로그램입니다.
1.숫자 뒤집기
(input)
12345
(output)
54321
(프로그램-1, 순환알고리즘)
#include<stdio.h>
#include<math.h>
int f(int p)
{
if(p==0)return 0;
printf("%d",p%10);
f(p/10);
return 0;
}
int main()
{
int n;
scanf("%d",&n);
f(n);
return 0;
}
(프로그램-2, 수학을 이용)
#include<stdio.h>
#include<math.h>
int f(int p)
{
if(p<10)return p;
return f(p/10)+(p%10) * powf(10.0,(int)log10((double)p));
}
int main()
{
int n,k;
scanf("%d",&n);
k = f(n);
printf("%d\n",k);
return 0;
}
(프로그램-3, 동적표를 이용)
#include<stdio.h>
#include<math.h>
int d[100001];
int f(int p)
{
if(p<10)return p;
if(!d[p]) d[p] = f(p/10)+(p%10) * powf(10.0,(int)log10((double)p));
return d[p];
}
int main()
{
int n,k;
scanf("%d",&n);
k = f(n);
printf("%d\n",k);
return 0;
}
2.조합
(input)
10 5
(ouput)
252
(프로그램-1, 순환알고리즘)
#include<stdio.h>
int f(int p, int q)
{
if(p==q)return 1;
if(q==1)return p;
return f(p-1,q-1) + f(p-1,q);
}
int main()
{
int n,k;
scanf("%d %d",&n, &k);
k = f(n,k);
printf("%d\n",k);
return 0;
}
(프로그램-2, 수학을 이용)
#include<stdio.h>
int f(int p, int q)
{
if(p==q)return 1;
if(q==1)return p;
return f(p,q-1)*(p-q+1)/q;
}
int main()
{
int n,k;
scanf("%d %d",&n, &k);
k = f(n,k);
printf("%d\n",k);
return 0;
}
(프로그램-3, 동적표를 이용)
#include<stdio.h>
int d[51][51];
int f(int p, int q)
{
if(p==q)return d[p][q]=1;
if(q==1)return d[p][q]=p;
if(!d[p][q]) d[p][q] = f(p,q-1)*(p-q+1)/q;
return d[p]q];
}
int main()
{
int n,k;
scanf("%d %d",&n, &k);
k = f(n,k);
printf("%d\n",k);
return 0;
}
3.1~n 합 구하기
(프로그램-1, 순환알고리즘)
#include<stdio.h>
int f(int n)
{
if(n==1) return 1;
return f(n-1)+n;
}
int main()
{
int n, k;
scanf("%d", &n);
k=f(n);
printf("%d\n",k);
return 0;
}
(프로그램-2, 수학을 이용)
#include<stdio.h>
int f(int n)
{
if(n==1) return 1;
return 2*f(n/2)+((n+1)/2)*((n+1)/2);
}
int main()
{
int n, k;
scanf("%d",&n);
k = f(n);
printf("%d\n",k);
return 0;
}
(프로그램-3, 동적표를 이용)
#include<stdio.h>
int d[100001];
int f(int n)
{
if(n==1) return 1;
if(!d[n]) d[n] = 2*f(n/2)+((n+1)/2)*((n+1)/2);
return d[n];
}
int main()
{
int n, k;
scanf("%d",&n);
k = f(n);
printf("%d\n",k);
return 0;
}
4. 피보나치 수열
(프로그램-1, 순환알고리즘)
#include<stdio.h>
int f(int n)
{
if(n<=2) return 1;
return f(n-1)+f(n-2);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n",f(n));
return 0;
}
(프로그램-2, 동적표를 이용)
#include<stdio.h>
int d[100001];
int f(int n)
{
if(n<=2) return 1;
if(!d[n]) d[n]= f(n-1)+f(n-2);
return d[n];
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n",f(n));
return 0;
}
5. 문제를 해결하세요!
[문제]
같은 크기의 정사각형 종이가 n장 있다.
이 종이들을 밑변을 평행하게 연결하여 몇 개를 나열했다.
맨 아래에 나열한 변의 길이는 바로 윗 변의 길이보다 같거나 길어야 한다.
n이 입력될 때 가능한 배치를 모두 구하시오!
단 숫자형태로 표현했을 ?, 사전순서로 내림차순으로 한줄에 하나씩 출력하시오.
(input)
5
(output)
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
(프로그램-1)
#include<stdio.h>
int a[30], cnt;
int min(int a, int b)
{
return a>b ? b:a;
}
int f(int n, int k)
{
if(n==0){
for(int i=0; i<cnt; i++) printf("%d ",a[i]);
puts(" ");
return 0;
}
for(int i=min(n,k); i>=1; i--){
a[cnt++]=i;
f(n-i, i);
cnt--;
}
return 0;
}
int main()
{
int n;
scanf("%d", &n);
f(n,n);
return 0;
}
|