e-olymp 2524. Строки Фибоначчи

26/05/2019 by Дария Даниленко

Задача

В математике достаточно часто применяются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей, но могут применяться и для задания последовательностей строк.

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи $F_{0} = a$, $F_{1} = b$, … . Они задаются следующим образом: $F_{0} = a$, $F_{1} = b$, $F_{i} = F_{i-2}F_{i-1}$, $i >1$. Первые семь строк Фибоначчи выглядят следующим образом: $a$, $b$, $ab$, $bab$, $abbab$, $bababbab$, $abbabbababbab$.

Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера $n$ растет очень быстро, поэтому задача нахождения всех символов строки $F_{n}$ требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.

Напишите программу, которая находит $k$-ый символ строки $F_{n}$.

Входные данные

Первая строка содержит количество тестов $t$ ($1 ≤ t ≤ 100$). Каждая из следующих $t$ строк содержит два целых числа $n$ и $k$ ($0 ≤ n ≤ 45$, $1 ≤ k ≤ |F_{n}|$, через $|F_{n}|$ обозначена длина строки $F_{n}$, позиции символов в строке нумеруются с единицы).

Выходные данные

Выведите $t$ строк, каждая из которых содержит $k$-ый символ строки $F_{n}$.

Тесты

Входные данные	Выходные данные
4 0 1 1 1 3 2 7 7	a b a a
1 10 15	a
6 45 6 38 30 6 5 24 40 0 1 2 2	b a b b a b

Код программы

#include <iostream>
using namespace std;

int fib[45];

char solve(int n, int k) {
    if (n == 0) return 'a';
    if (n == 1) return 'b';
    if (k <= fib[n - 2]) return solve(n - 2, k);
    return solve(n - 1, k - fib[n - 2]);
}

int main() {
    int n, k, tests;
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];
    cin >> tests;
    while (tests--) {
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int fib[45];

char solve(int n, int k) {

if (n == 0) return 'a';

if (n == 1) return 'b';

if (k <= fib[n - 2]) return solve(n - 2, k);

return solve(n - 1, k - fib[n - 2]);

}

int main() {

int n, k, tests;

fib[0] = 1;

fib[1] = 1;

for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];

cin >> tests;

while (tests--) {

cin >> n >> k;

cout << solve(n, k) << endl;

}

return 0;

}

Решение

Воспользуемся тем, что длина $i$-той строки Фибоначчи будет равна $i$-тому числу Фибоначчи, так как для них справедливо одно и то же рекуррентное соотношение. Заводим массив fib[45]; , куда мы вычислим первые ($n ≤ 45$) числа Фибоначчи. Функция solve(int n, int k) находит $k$-ый символ строки $F_{n}$: так как $F_{i} = F_{i-2}F_{i-1}$, то если $k ≤ |F_{n-2}|$, то $k$-ый символ строки следует искать в $F_{n-2}$, в другом случае следует искать $(k — F_{n-2})$-ый символ в $F_{n-1}$. Таким образом, постепенно углубляясь в рекурсию, программа будет иметь дело с задачами все меньших размеров, пока наконец не выйдет на одну из единичных строк ( n == 0 или n == 1 ), и не выведет $a$ или $b$ соответственно.

Ссылки

Условие задачи на E-olymp

Код программы на IdeOne

Related Images:

MLoop22

31/10/2015 by Молоканов Юрий

Условие

Вычислите с точностью [latex]\varepsilon[/latex] сумму ряда [latex]\sum_{i=1}^{\infty} \frac {(-1)^i}{i^2}[/latex].

Тестирование

№	Входные данные	Выходные данные
1	1	-1
2	0.25	-0.75
3	0.1	-0.861111
4	0.01	-0.827962
5	0.0000001	-0.822467

Код

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	double a = -1, sum = -1, E;	// Объявляем переменные для члена ряда, суммы и точности, присваиваем первым двум значение первого члена ряда 
	cin >> E;
	for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++)	// Повторяем цикл, пока значение очередного члена ряда по модулю не меньше заданной точности
		sum += a;	// Накапливаем сумму
	cout << sum;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a = -1, sum = -1, E; // Объявляем переменные для члена ряда, суммы и точности, присваиваем первым двум значение первого члена ряда

cin >> E;

for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++) // Повторяем цикл, пока значение очередного члена ряда по модулю не меньше заданной точности

sum += a; // Накапливаем сумму

cout << sum;

return 0;

}

Решение

Вычисление суммы ряда с точностью [latex]\varepsilon[/latex] представляет собой процесс нахождения членов ряда и их суммирования до тех пор, пока значение очередного члена по модулю не окажется меньше указанной точности.

Прежде всего найдем зависимость [latex]a_{n+1}[/latex] от [latex]a_n[/latex] и выведем рекуррентную формулу для очередного члена:

[latex]a_{n+1} = a_n \cdot \frac {a_{n+1}}{a_n} = a_n \cdot \frac {\frac {(-1)^{i+1}}{(i+1)^2}}{\frac {(-1)^i}{i^2}} = a_n \cdot -(\frac {i}{i+1})^2[/latex]

Для вычислений мы используем рекуррентное соотношение, поэтому до выполнения цикла, накапливающего сумму, переменным члена ряда a и суммы sum потребуется присвоить значение [latex]a_1 = \frac {(-1)^1}{1^2} = -1[/latex]:

double a = -1, sum = -1, E;

1	double a = -1, sum = -1, E;

Теперь опишем, каким образом будет работать цикл:

Цикл будет начинаться со счетчиком [latex]i = 1[/latex], который будет инкрементироваться в конце каждой итерации.
Цикл будет выполняться до тех пор, пока абсолютное значение очередного члена ряда [latex]a_i[/latex] будет не меньше, чем заданная точность [latex]\varepsilon[/latex].
В каждой итерации цикла значение суммы будет увеличиваться на [latex]a_i[/latex].

Реализуем описанный алгоритм с помощью цикла for. Чтобы сократить количество операций в теле цикла до одной, вычислять очередной член ряда будем при проверке выполнения условия продолжения. При присвоении переменной a нового значения воспользуемся кастингом (double) ; в противном случае уже второй член ряда будет обнуляться из-за умножения на дробь с целой частью [latex]0[/latex]:

for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++)
	sum += a;

1 2	for(int i = 1; abs(a = (double)(-ii)/(i+1)/(i+1)) >= E; i++) sum += a;

Наконец, выведем требуемое значение — сумму ряда:

cout << sum;

1	cout << sum;

Ссылки

Код программы на Ideone.com;

Список задач на циклы.

Related Images:

Ю3.19

26/11/2014 by Григорян Артак

Для заданных [latex]a[/latex] и [latex]p[/latex] вычислить [latex]\sqrt[p]{a}[/latex], используя рекуррентную формулу:

[latex]x_{n+1}=\frac{x_{n}}{p^{2}}[(p^{2}-1)+\frac{1}{2}(p+1)\frac{a}{x_{n}^{p}}-\frac{1}{2}(p-1)\frac{x_{n}^{p}}{a}][/latex];

Сколько итераций надо выполнить, чтобы для заданной погрешности [latex]\varepsilon[/latex] было справедливо соотношение [latex]\mid x_{n+1}-x_{n} \mid [/latex] [latex] \leq[/latex][latex]\varepsilon[/latex]?При каких начальных приближениях [latex]x_{0}[/latex] процесс сходится?

a	p	xz	eps	i	xn	x	Комментарий
16	4	1	0.000001	5	4	4
17	2	2	0.01	3	4.12311	4.12311
26	4	12	0.1	—	—	—	Превышено ограничение на время

Код программы:

#include <iostream>
#include <math.h>
using namespace std;

int main () 
{
    double a,xz,eps;
    int p;
    cin>>a>>p>>xz>>eps;
    double x=pow(a,1.0/p);
    double xn=xz,x_prev=-10000000;
    int i=0;
    while (fabs(xn-x_prev)>=eps)
    {  
        x_prev=xn;
        xn=(x_prev/(p*p))*((p*p-1)+0.5*(p+1)*a/(pow(x_prev,p))-0.5*(p-1)*pow(x_prev,p)/(a));
        i++;
       
    }
    cout<<i<<' '<<xn<<' '<<x<<endl; 
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main ()

{

double a,xz,eps;

int p;

cin>>a>>p>>xz>>eps;

double x=pow(a,1.0/p);

double xn=xz,x_prev=-10000000;

int i=0;

while (fabs(xn-x_prev)>=eps)

{

x_prev=xn;

xn=(x_prev/(p*p))*((p*p-1)+0.5*(p+1)*a/(pow(x_prev,p))-0.5*(p-1)*pow(x_prev,p)/(a));

i++;

}

cout<<i<<' '<<xn<<' '<<x<<endl;

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in=new Scanner(System.in);
		double a=in.nextDouble();
		int p=in.nextInt();
		double xz=in.nextDouble();
		double eps=in.nextDouble();
		double x=Math.pow(a,1.0/p);
		double xn=xz,x_prev=-10000000;
    	int i=0;
		while (Math.abs(xn-x_prev)>=eps)
		{  
    		x_prev=xn;
       		xn=(x_prev/(p*p))*((p*p-1)+0.5*(p+1)*a/(Math.pow(x_prev,p))-0.5*(p-1)*Math.pow(x_prev,p)/(a));
    		i++;
       
    	}
    	System.out.print(i);System.out.print(" ");
    	System.out.print(xn);System.out.print(" ");
    	System.out.println(x);
   
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in=new Scanner(System.in);

double a=in.nextDouble();

int p=in.nextInt();

double xz=in.nextDouble();

double eps=in.nextDouble();

double x=Math.pow(a,1.0/p);

double xn=xz,x_prev=-10000000;

int i=0;

while (Math.abs(xn-x_prev)>=eps)

{

x_prev=xn;

xn=(x_prev/(p*p))*((p*p-1)+0.5*(p+1)*a/(Math.pow(x_prev,p))-0.5*(p-1)*Math.pow(x_prev,p)/(a));

i++;

}

System.out.print(i);System.out.print(" ");

System.out.print(xn);System.out.print(" ");

System.out.println(x);

}

Вводим с клавиатуры [latex]a[/latex], [latex]p[/latex], [latex]xz[/latex], [latex]eps[/latex], где [latex]xz[/latex]- наше приближение [latex]x_{0}[/latex], а [latex]eps[/latex] заданная погрешность.
С помощью цикла и рекуррентно заданной формулы получаем [latex]xn[/latex].С помощью счетчика [latex]i[/latex] получаем количество итераций.
Если программа вычисляет слишком долго, то мы можем сказать, что процесс не сходится.

Код программы можно посмотреть тут

Related Images:

A114з

15/11/2014 by Чежеумова Анна

Задача:

Вычислить [latex]\prod_{i=2}^{10}{\left(1-\frac{1}{i!} \right)^{2}}[/latex].

Тест:

[latex]\prod_{i=2}^{10}{\left(1-\frac{1}{i!} \right)^{2}}=0,1563[/latex]- тест пройден.

#include <stdio.h>

int main() 
{
	double p=1;
	double a=1;
	for (int i=2; i<=10; i++)
	{
		a*=i;
		p*=(1.0-1.0/a)*(1.0-1.0/a);
	}
	printf("p= %0.4lf", p);
	return 0;
}

#include <stdio.h>

int main()

{

double p=1;

double a=1;

for (int i=2; i<=10; i++)

{

a*=i;

p*=(1.0-1.0/a)*(1.0-1.0/a);

}

printf("p= %0.4lf", p);

return 0;

}

Решение:

Для решения это задачи сделаем цикл. в котором будем вычислять произведение и факториал. Факториал будем вычислять применяя рекуррентные соотношения. Затем подставим факториал в формулу и вычислим произведение.

Посмотреть работу программы можно здесь.

Related Images:

Ю3.20

01/11/2014 by Марченко Філіп Олександрович

Задача: Для заданных [latex]a[/latex] и [latex]p[/latex] вычислить [latex]x = \sqrt[p]{a}[/latex] по рекуррентному соотношению Ньютона:

[latex]x_{n+1}=\frac{1}{p}*\left[(p-1)x_{n}+\frac{a}{x_{n}^{p-1}}\right][/latex] [latex]x_{0} = a[/latex]

Сколько итераций надо выполнить, чтобы для достижения заданной погрешности [latex]\varepsilon[/latex] выполнялось соотношение:

[latex]\left|x_{n+1}-x_{n}\leq\varepsilon\right|[/latex]?

Тесты:

[latex]a[/latex]	[latex]p[/latex]	Значение корня [latex]x[/latex]	Значение корня [latex]x[/latex], подсчитанного с помощью соотношения	Количество итераций
57	5	2.24479	2.24479	18
16	2	4	4	5
230	2	15.1658	15.1658	7
9	3	2.08008	2.08008	7

Код на С++:

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;
double pow_b (double a, int n){
    if (n==0) return 1;
    double result = 1;
    while (n>0) {
        if (n%2==0) {
            n/=2;
            a*=a;
        }
        else {
            n--;
            result*=a;
        }
    }
    return result;
}
int main () {
    double a, p, eps=0.00001; //инициализируем переменные и задаём погрешность
    cin>>a>>p;
    double x=pow(a, 1/p);  //подсчитываем значение
    double xn=a, x_prev;
    int i=0;
    while (fabs(x-xn) > eps){  //создаём цикл, котоый считает значение с помощью рекурентного соотношения Ньютона
        x_prev=xn;
        xn=(1/p)*(x_prev*(p-1) + a/(pow_b(x_prev, p-1)));
        i++;
    }
    cout<<i<<' '<<xn<<' '<<x; //выводим количество итераций на экран.
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <math.h>

using namespace std;

double pow_b (double a, int n){

if (n==0) return 1;

double result = 1;

while (n>0) {

if (n%2==0) {

n/=2;

a*=a;

}

else {

n--;

result*=a;

}

return result;

}

int main () {

double a, p, eps=0.00001; //инициализируем переменные и задаём погрешность

cin>>a>>p;

double x=pow(a, 1/p); //подсчитываем значение

double xn=a, x_prev;

int i=0;

while (fabs(x-xn) > eps){ //создаём цикл, котоый считает значение с помощью рекурентного соотношения Ньютона

x_prev=xn;

xn=(1/p)*(x_prev*(p-1) + a/(pow_b(x_prev, p-1)));

i++;

}

cout<<i<<' '<<xn<<' '<<x; //выводим количество итераций на экран.

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;


class Ideone {
	public static double bPow (double a, double n){
		if (n==0) return 1;
	    double result = 1;
	    while (n>0) {
	        if (n%2==0) {
	            n/=2;
	            a*=a;
	        }
	        else {
	            n--;
	            result*=a;
	        }
	    }
    	return result;
	}
	public static void main (String[] args)	{
		Scanner sc = new Scanner (System.in);
		int Iterations = 0;
		double eps = sc.nextDouble();
		double a = sc.nextDouble();
		double p = sc.nextDouble();
		double x = a;
		double x_next = (1 / p) * ( (p - 1) * x + a / bPow(x, p - 1)) ;
		while (Math.abs(x_next - x) > eps) {
			x = x_next;
			x_next = (1 / p)*((p - 1) * x + a / (bPow(x, p - 1)) );
			Iterations++;
		}
		System.out.println("Result: " + x_next + "; Iterations: " + Iterations);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static double bPow (double a, double n){

if (n==0) return 1;

double result = 1;

while (n>0) {

if (n%2==0) {

n/=2;

a*=a;

}

else {

n--;

result*=a;

}

return result;

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int Iterations = 0;

double eps = sc.nextDouble();

double a = sc.nextDouble();

double p = sc.nextDouble();

double x = a;

double x_next = (1 / p) * ( (p - 1) * x + a / bPow(x, p - 1)) ;

while (Math.abs(x_next - x) > eps) {

x = x_next;

x_next = (1 / p)*((p - 1) * x + a / (bPow(x, p - 1)) );

Iterations++;

}

System.out.println("Result: " + x_next + "; Iterations: " + Iterations);

}

Решение: Для подсчёта значения корня с помощью рекуррентного соотношения, я создал цикл, в котором организовал подсчёт значения таким образом, что пока разница значения корня x, подсчитанного с помощью функции pow, cо значением текущего корня xn, подсчитанным с помощью соотношения, больше заданной погрешности eps, то, записывая текущее значение в переменную x_prev, подсчитываю новое значение корня. В зависимости от заданной погрешности, программа считает результат и выводит его на экран вместе с кол-вом итераций.

UPD: По предложению Игоря Евгеньевича добавил быстрое возведение в целую степень.

Решение UPD: Чтобы построить алгоритм быстрого возведения в степень, необходимо рассмотреть две ситуации:

Когда степень чётна;
Когда степень не чётна;

Ситуация 1 : Проведя несложный анализ можно заметить, что [latex]{a}^{p}[/latex] можно представить в виде

[latex](a^{\frac{p}{2}})^{2}[/latex].

Ситуация 2: В этой ситуации необходимо перейти в степень [latex]p-1[/latex], которая является чётной.

[latex]a^{p}=a^{p-1} * a[/latex]

И в результате получим алгоритм, который работает за [latex]O(\log n)[/latex].

Проверить правильность работы программы можно здесь (UPD): http://ideone.com/VBLGKO

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: Рекуррентное соотношение

e-olymp 2524. Строки Фибоначчи

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение

Ссылки

Related Images:

MLoop22

Условие

Тестирование

Код

Решение

Ссылки

Related Images:

Ю3.19

Related Images:

A114з

Related Images:

Ю3.20

Related Images: