Блог

Главная - Python язык программирования - Программа на Python для n-го кратного числа в ряду Фибоначчи
You are currently viewing Программа на Python для n-го кратного числа в ряду Фибоначчи

Программа на Python для n-го кратного числа в ряду Фибоначчи

Даны два целых числа n и k. Найдите положение n-го кратного K в ряду Фибоначчи.

Примеры:

Входные данные : k = 2, n = 3
Выход : 9
3-е кратное 2 в ряду Фибоначчи равно 34 
который появляется в позиции 9.

Входные данные : k = 4, n = 5 
Выход : 30
5-е кратное 5 в ряду Фибоначчи равно 832040 
который появляется в позиции 30.

Эффективное решение основано на следующем интересном свойстве.
Ряд Фибоначчи всегда является периодическим при модульном представлении. Ниже приведены примеры.

F (mod 2) = 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,
 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0 
Here 0 is repeating at every 3rd index and 
the cycle repeats at every 3rd index. 

F (mod 3) = 1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0
 ,1,1,2,0,2,2,1,0,1,1,2,0,2,2
Here 0 is repeating at every 4th index and 
the cycle repeats at every 8th index.

F (mod 4) = 1,1,2,3,1,0,1,1,2,3,1,0,1,1,2,3,
 1,0,1,1,2,3,1,0,1,1,2,3,1,0 
Here 0 is repeating at every 6th index and 
the cycle repeats at every 6th index.

F (mod 5) = 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,
 2,2,4,1,0,1,1,2,3,0,3,3,1,4,0
Here 0 is repeating at every 5th index and
the cycle repeats at every 20th index.

F (mod 6) = 1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,
 3,1,4,5,3,2,5,1,0,1,1,2,3,5,2
Here 0 is repeating at every 12th index and 
the cycle repeats at every 24th index.

F (mod 7) = 1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,
 0,1,1,2,3,5,1,6,0,6,6,5,4,2,6 
Here 0 is repeating at every 8th index and 
the cycle repeats at every 16th index.

F (mod 8) = 1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,
 3,5,0,5,5,2,7,1,0,1,1,2,3,5,0 
Here 0 is repeating at every 6th index and 
the cycle repeats at every 12th index.

F (mod 9) = 1,1,2,3,5,8,4,3,7,1,8,0,8,8,7,
 6,4,1,5,6,2,8,1,0,1,1,2,3,5,8 
Here 0 is repeating at every 12th index and 
the cycle repeats at every 24th index.

F (mod 10) = 1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,
 7,7,4,1,5,6,1,7,8,5,3,8,1,9,0.
Here 0 is repeating at every 15th index and
the cycle repeats at every 60th index.
# Python Program to find position of n\'th multiple
# of a number k in Fibonacci Series

def findPosition(k, n):
	f1 = 0
	f2 = 1
	i =2;
	while i!=0:
		f3 = f1 + f2;
		f1 = f2;
		f2 = f3;

		if f2%k == 0:
			return n*i

		i+=1
		
	return


# Multiple no.
n = 5;
# Number of whose multiple we are finding
k = 4;

print("Position of n\'th multiple of k in"
				"Fibonacci Series is", findPosition(k,n));

# Code contributed by Mohit Gupta_OMG

Выход:

Position of n'th multiple of k inFibonacci Series is 30

Выход:

Position of n'th multiple of k inFibonacci Seires is 30
Метки: