Using the concise C language code to solve the problem of step jumping and Joseph ring

Step jumping problem

Topic:

There are a total of n steps on each step. If you can jump 1 step in one time, you can also jump 2 steps.

Find out how many total hops there are, and analyze the time complexity of the algorithm.

Analysis:

It is also a relatively basic problem, which can be solved easily through recursion

The code is implemented as follows (GCC is compiled and passed) :

#include "stdio.h"
#include "stdlib.h"
 
int function(int n);
 
int main(void)
{
  int tmp;
   
  tmp = function(5);
  printf("%3d\n",tmp);
 
  return 0;
}
 
int function(int n)
{
  if(n == 1)
    return 1;
  else if(n == 2)
    return 2;
  else  
    return function(n-1) + function(n-2);
}

Joseph ring problem
Topic:

n Numbers (0,1,... , n-1) form a circle, starting with the number 0, and delete the m number from the circle each time (the first is the current number itself, and the second is the next number of the current number). When a number is deleted, the m number continues to be deleted from the next number to be deleted. Find the last number left in the circle.

(that's the Joseph ring problem.)

Analysis:

I also saw the problem of Joseph ring when I was learning linked list before. At that time, I simulated the whole process of the linked list to solve it. Today, I saw a kind of analysis on the Internet. Write it down:

      asks for the last remaining number (represented by last), which is the number in the (0,1,... What is the position of n-1). We know what they're talking about, so we're going to generalize this number. Assuming that we know the position of this number in the remaining number k, how can we find its position in the remaining number K+1? In this way, step by step, we deduce its position in the number n. Why is this possible? Because this last number is lucky enough to survive all the deletions, except that every time one is deleted, its position changes, until at the end, its position is zero (there is only one left).

Now let's analyze the relationship between the position of the number last and the position of the number last. Of these n Numbers, the first number to be deleted is (m-1)%n, which is called k for simplicity. Then the number n-1 left after k is 0,1... k, k - 1, + 1,... , n-1, and the next starting number is k+1. Equivalent to the remaining sequence, k+1 to the front, thus forming the sequence k+1... n - 1, 0,... k - 1.

k+1       - >       0
k+2       - >       1
...
n-1       - >       n-k-2
0             - >       n-k-1
...
k-1     - >     n-2

Now that we know where last is with the number n-1, f(n-1,m), how do we find the relationship between f(n,m) and f(n-1,m)? It is represented by X and Y, as follows:

Y                           X

k+1       - >       0
k+2       - >       1
...
n-1       - >       n-k-2
0             - >         n-k-1
...
k-1       - >       n-2

y=( x+k+1) %n

k = (m-1)%n

So y=(x+m)%n, and the final relationship is as follows:

                              0                                                           n=1
f(n,m)={
                              [f(n-1,m)+m]%n         n > 1

It's easy to get code based on relationships

The code is implemented as follows:

int LastRemaining(int n, int m)
{
  if(n < 1 || m < 1)
    return -1;
 
  int last = 0;
  for (int i = 2; i <= n; i ++) 
    last = (last + m) % i;
 
  return last;
}