The algorithm you are trying to solve is
- The first is 1, the second is 2, and the third is the remaining sequence divided by 100.
Write a program that outputs the Nth value using a recursive function by receiving N of a natural number 100.
Input: 5
Output: 8
(1 2 2 4 8 32 56 92 ..)
#include <stdio.h>
int Rem(int N)
{
if(N == 1)
return 1;
if(N == 2)
return 2;
return Rem(N-1) * Rem(N-2) % 100;
}
int main(void)
{
int N;
scanf("%d", &N);
printf("%d", Rem(N));
return 0;
}
Return 1 or 2 when N becomes 1 or 2 as a recursive function. So the first value is 1 and the second value is 2.
Then 1 2 is obtained, so as we saw in the question, (N-1 * N-2)%100 is obtained from the third time. Obtain returnRem(N-1) *Rem(N-2)%100; as a recursive function.
TIME LIMIT AXCEED appears when this code is scored on the Jung All site. Timeout, right?
I'm trying to make a memo, but I don't understand.
I'm looking for someone who can explain it step by step ㅠ<
#include <stdio.h>
int recur(int n, int *arr){
if (n == 1){
return 1;
}
else if (n == 2){
arr[0] = 1;
return 2;
}else{
arr[n-2] = recur(n-1, arr);
return arr[n-2] * arr[n-3] % 100;
}
}
int main() {
int n;
scanf("%d", &n);
int arr[n];
printf("%d\n", recur(n, &arr));
return 0;
}
I could've written it in a cleaner way, but I checked if it worked
If you call yourself twice in a recursive function, the larger the number, the more you call yourself, so we use memoization.
After declaring an array by the size of the input, the first two cases return 1 and 2, and the remaining cases call the recursive function that reduces n by 1, and store it in the next column of the array and return the remainder divided by 100, as required in the problem.
(I can't find the space to ask questions...) I'm asking a question here) Uh, it's a different question from this one. What level do you think this algorithm is? In case of heavy load
© 2024 OneMinuteCode. All rights reserved.