C 3차시 과제

-1535- 문제 

---

*주의사항 : 이 (함수 제출형) 문제는 함수 부분만 작성해서 제출해야 오류 없이 채점이 됩니다.
미리 작성되어있는 코드를 읽고 해석해서, 함수 부분만 작성해서 제출하면 됩니다.
작성한 함수의 테스트를 위해서는 제시된 코드를 복사해 사용하면 되고, 제출은 함수 부분만 하세요.

------

배열에서 가장 큰 값이 처음 나타나는 위치를 출력하시오.

단, 함수형 문제이므로 함수 f()만 작성하시오.

[함수형 문제란??]
함수형 문제는 기본적인 main() 등은 미리 작성되어 있습니다.
미리 작성되어 있는 프로그램은 다음과 같습니다.

미리 작성된 프로그램을 복사해 붙여 넣은 후 함수 부분을 설계하여 작성해 넣고,
테스트 한 후, 함수 부분만 제출하세요.

[미리 작성된 프로그램] - C/C++로 제출하는 경우에만 추가됩니다.

#include <stdio.h>
 
int n, d[110];
 
// 이 부분에 들어가야 될 코드를 작성하여 제출
int main()
{
  scanf("%d", &n);
 
  for(int i=0; i<n; i++)
    scanf("%d", &d[i]);
 
  printf("%d", f());
  return 0;
}

-1535- 풀이

---

포맷 스트링 %d를 통해서 f()함수가 int 형의 리턴 값을 가질 수 있다는 것을 알 수 있습니다.
for문을 사용해서 0부터 n-1까지 돌리고, d[max]의 값과 d[i]값을 비교해서 d[i]가 더 크면 max가 i로 바뀌도록 작성했습니다.

max를 인덱스 값으로 설정하여 필요한 인덱스만 가져올 수 있도록 했습니다.
결론적으로 더 큰 값이 올때만 max가 바뀌기 때문에, 가장 큰 값이 처음 나타나는 위치를 알 수 있습니다.
문제의 조건이 가장 큰 값이 첫 번째 인덱스일때 0이 아니라 1로 나타냈기 때문에 max에 1을 더했습니다.

int f(){
    int max=0;
    for(int i=0;i<n;i++){
        if(d[i]>d[max])max=i;
    }
    return max+1;
}

-1555- 문제

---

*주의사항 : 이 (함수 제출형) 문제는 함수 부분만 작성해서 제출해야 오류 없이 채점이 됩니다.
미리 작성되어있는 코드를 읽고 해석해서, 함수 부분만 작성해서 제출하면 됩니다.
작성한 함수의 테스트를 위해서는 제시된 코드를 복사해 사용하면 되고, 제출은 함수 부분만 하세요.

------

int 형 정수 한 개를 입력 받아
1부터 n까지의 정수합을 계산해 출력하시오.
(0 <= n <= 10000000)

단, 함수형 문제이므로 함수 f()만 작성하여 제출하시오.


[함수형 문제란??]
함수형 문제는 기본적인 main() 등은 미리 작성되어 있습니다.
미리 작성되어 있는 프로그램은 다음과 같습니다.

미리 작성된 프로그램을 복사해 붙여 넣은 후 함수 부분을 설계하여 작성해 넣고,
테스트 한 후, 함수 부분만 제출하세요.

[미리 작성된 프로그램] - C/C++로 제출하는 경우에만 추가됩니다.

 

 

#include <stdio.h>
 
int n;
 
// 이 부분에 들어가야 될 코드를 작성하여 제출
 
int main()
{
  scanf("%d", &n);
  printf("%lld\n", f(n));
}

-1555- 풀이

---

문제의 조건을 가장 먼저 확인했습니다. n의 값이 0 <= n <= 10,000,000 인것을 확인할 수 있었습니다.
n의 범위를 통해서 당연히 함수의 반환 값이 int 정도로는 부족한 것을 알 수 있습니다. 왜냐하면 int는 –2,147,483,648 ~ 2,147,483,647의 범위를 가지고 있기 때문입니다. 그리고 아래 main함수에 대놓고 %lld를 사용하니 long long형을 리턴해줘야한다고도 알 수 있습니다.

https://opentutorials.org/module/3921/23557

long long형으로 리턴하기 위해서 sum변수를 long long으로 선언했습니다.
for문을 사용해서 1부터 n까지 돌리면서 sum에 값을 더해줬습니다.
n은 전역변수라서 f()함수 내부에서 사용이 가능합니다.

long long f(int a){
    long long sum=0;
    for(int i=1;i<=a;i++){
        sum+=i;
    }
    return sum;
}

-1566- 문제

---

*주의사항 : 이 (함수 제출형) 문제는 함수 부분만 작성해서 제출해야 오류 없이 채점이 됩니다.
미리 작성되어있는 코드를 읽고 해석해서, 함수 부분만 작성해서 제출하면 됩니다.
작성한 함수의 테스트를 위해서는 제시된 코드를 복사해 사용하면 되고, 제출은 함수 부분만 하세요.

------

int 형 자연수 두 개(a, n)를 입력 받아
거듭 제곱(exponentiation, a^n)한 결과 값을 출력하시오.

단, 함수형 문제이므로 함수 pow()만 작성하여 제출하시오.

참고
수학식 a^n 으로 표현되는 거듭 제곱은 a를 n번 거듭 곱한 수를 의미한다.
예를 들어 2^10 은 2를 10번 거듭해서 곱한 값을 의미하며 1024이다.


[함수형 문제란??]
함수형 문제는 기본적인 main() 등은 미리 작성되어 있습니다.
미리 작성되어 있는 프로그램은 다음과 같습니다.

미리 작성된 프로그램을 복사해 붙여 넣은 후 함수 부분을 설계하여 작성해 넣고,
테스트 한 후, 함수 부분만 제출하세요.

[미리 작성된 프로그램] - C/C++로 제출하는 경우에만 추가됩니다.

#include <stdio.h>
 
int a, n;
// 이 부분에 들어가야 될 코드를 작성하여 제출
int main()
{
  scanf("%d%d", &a, &n);
  printf("%lld\n", pow(a, n));
}

---

%lld를 통해서 long long형의 리턴 값을 가지는 pow()라는 함수를 작성해야한다는 것을 알 수 있습니다.
pow(a,b)를 통해 매개변수가 두개가 필요한 함수인것도 알 수 있습니다.
문제에 int 형 자연수 두개라고 조건이 주어진 것을 통해서 매개변수 두개가 int형인 것을 알 수 있습니다.

먼저 for문을 사용하면서 곱해주는 방식을 통해서 거듭제곱을 계산하는 방식을 사용했습니다.
처음 짠 코드인데 시간 초과라고 떴습니다. 그래서 간단한 계산이지만 연산을 쓸데없이 많이하는 케이스들을 예외 처리하였습니다.

long long pow(int m,int n){
    long long res= 1;
    for(int i=0;i<n;i++){
        res*=m;
    }
    return res;
}

long long pow(int m,int n){
    long long res= 1;
    if(n==0)return res;
    else if(m==1)return res;
    
    for(int i=0;i<n;i++){
        res*=m;
    }
    return res;
}

-1916- 문제

---

피보나치 수열이란 앞의 두 수를 더하여 나오는 수열이다.
첫 번째 수와 두 번째 수는 모두 11이고, 세 번째 수부터는 이전의 두 수를 더하여 나타낸다. 피보나치 수열을 나열해 보면 다음과 같다.

1,1,2,3,5,8,13…1,1,2,3,5,8,13…

자연수 N을 입력받아 N번째 피보나치 수를 출력하는 프로그램을 작성하시오.
단, N이 커질 수 있으므로 출력값에 10,009를 나눈 나머지를 출력한다. (N은 200보다 작거나 같다.)
※ 이 문제는 반드시 재귀함수를 이용하여 작성 해야한다.

금지 키워드 : while goto for

 

 

-1916- 풀이

---

피보나치 수열은 1 1 2 3 5 8 13 .... 이런식으로 커진다.
2보다 큰 자연수 n에 대해서 수열 a(n)은 귀납적으로 a(n)=a(n-1)+a(n-2)로 표현될 수 있다.
첫째 항과 둘째 항은 1이기 때문에 배열에 1을 넣어줬다.

이미 첫째 항과 둘째 항을 넣어줘서 굳이 a==1같은 조건식은 생략해줬습니다. 
문제에서 출력을 보니, 인덱스가 1부터 시작이라서 -1을 해줬다.

#include<stdio.h>
int arr[200]={1,1};
int f(int);
int main(){
  int n=0; 
  scanf("%d",&n);
  printf("%d\n",f(n));
}
int f(int a){
  if(a<=2)return arr[a-1];
  if(arr[a-1]!=0)return arr[a-1];
  return arr[a-1]=(f(a-1)+f(a-2))%10009;
}

콜라츠의 추측, 3n+1 문제, 우박수 문제라고 불리는 이 문제는 다음과 같다.
1, 어떤 자연수 n이 입력되면,
2. n이 홀수이면 3n+1을 하고,
3. n이 짝수이면 n/2를 한다.
4. 이 n이 1이 될때까지 2~3과정을 반복한다.
예를 들어 5는 5 → 16 → 8 → 4 → 2 → 1 이 된다.
여기서 5가 1이되기 위해 6개의 숫자를 나열하게 된다. 이것을 길이라고 하면 5의 길이는 6이된다.
시작수와 마지막 수가 입력되면 그 두 사이게 길이가 가장긴 우박수와 그 길이를 출력하시오. (1 <= a <= b <= 10,000,000)

 

-3733- 풀이

---

처음에 작성한 코드이다.
단순히 9,999,999 * 3 + 1을 해보면 범위를 넘어가는 것을 알 수 있다.
제출해보니, segment fault 에러가 났다. 아마 자료형도 문제지만, 배열에 대해서도 잘못된 접근이 있다고 생각했다.

자료형을 고쳤고, n이 10,000,000보다 큰 값이 나올 수 있어서 if문으로 n의 크기를 확인했다.

#include<stdio.h>
int m,M;
int max;
unsigned int arr[10000001]={0,1,2};
unsigned int ubak(unsigned n){
  if(arr[n]!=0)return arr[n];
  else if(n%2==0)return arr[n]=ubak(n/2)+1;
  else return arr[n]=ubak(3*n+1)+1;
}
 
int main(){
  scanf("%d %d",&m,&M);
  for(int i=m;i<=M;i++){
    if(arr[max]<ubak(i))max=i;
  }
  printf("%d %u",max,arr[max]);
}

unsigned long long arr[10000001]={0,1,2};  부분을 unsigned long long arr[10000001];으로 고쳤더니 갑자기 에러가 뜨지 않았다.

그래서 n==1을 비교하는 부분을 추가하고 제출했더니 정답이였다.

#include<stdio.h>
unsigned long long arr[10000001];
unsigned long long ubak(unsigned long long n){
  if(n>10000000){
    if(n%2==0)return ubak(n/2)+1;
    else return ubak(3*n+1)+1;
  }
  else{
    if(n==1)return 1;
    if(arr[n]!=0)return arr[n];
    else if(n%2==0)return arr[n]=ubak(n/2)+1;
    else return arr[n] = ubak(3*n+1)+1;
  }
  
}
int main(){
  int m,M;
  unsigned long long max=0;
  int index;
  scanf("%d %d",&m,&M);
  for(int i=m;i<=M;i++){
    if(max<ubak(i)){
      max=ubak(i);
      index = i;
    }
  }
  printf("%d %llu",index,max);
}