e-olymp 1210. Очень просто!!!

04/12/2017 by Вадим Гордийчук

Задача

По заданным числам [latex]n[/latex] и [latex]a[/latex] вычислить значение суммы: [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex]

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

Два натуральных числа [latex]n[/latex] и [latex]a[/latex].

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

Значение суммы. Известно, что оно не больше [latex]10^{18}[/latex].

Тесты

Входные данные	Выходные данные
3 3	102
4 4	1252
9 3	250959
7 14	785923166
1009 1	509545

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

#include <iostream>
using namespace std;

int main()
{
    unsigned long long int n, a, answer;
    cin >> n >> a;
    if (a > 1)
    {
        answer = n*a;
        for(unsigned long long int i = n-1; i > 0; --i)
            answer = (answer+i)*a;
    }
    else
        answer = n*(n+1)/2;
    cout << answer;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned long long int n, a, answer;

cin >> n >> a;

if (a > 1)

{

answer = n*a;

for(unsigned long long int i = n-1; i > 0; --i)

answer = (answer+i)*a;

}

else

answer = n*(n+1)/2;

cout << answer;

return 0;

}

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

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextInt(), a = in.nextInt(), ans;
        if (a > 1)
        {
            ans = n*a;
            for(long i = n-1; i > 0; --i)
                ans = (ans+i)*a;
        }
        else
            ans = n*(n+1)/2;
        System.out.println(ans);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

long n = in.nextInt(), a = in.nextInt(), ans;

if (a > 1)

{

ans = n*a;

for(long i = n-1; i > 0; --i)

ans = (ans+i)*a;

}

else

ans = n*(n+1)/2;

System.out.println(ans);

}

Решение задачи

Данную задачу можно решить прямым линейным вычислением значений элементов заданного ряда, то есть получать значение элемента ряда с индексом [latex]i[/latex] умножением [latex]a[/latex] (которое необходимо возвести в степень [latex]i[/latex]) на индекс [latex]i[/latex] и накапливать сумму этих значений в выделенной переменной.
Но безусловно такое решение не является качественным (даже если будет использован алгоритм бинарного возведения в степень).

Для получения качественного решения распишем ряд подробно:
[latex]A[/latex] [latex]=[/latex] [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex] [latex]=[/latex] [latex]a+2a^2+3a^3+\ldots+\left( n-1 \right) a^{n-1}+na^{n}[/latex] [latex]=[/latex] [latex]na^{n}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-1}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{3}[/latex] [latex]+[/latex] [latex]2a^2[/latex] [latex]+[/latex] [latex]a[/latex].
Очевидно, что из полученного выражения можно вынести [latex]a[/latex] за скобки. Применим данную операцию:
[latex]A[/latex] [latex]=[/latex] [latex] \left( na^{n-1}+\left( n-1 \right)a^{n-2}+\ldots+3a^{2}+2a+1\right) \cdot a[/latex] Из полученной формулы видно, что аналогичное действие можно применить вновь, для внутреннего выражения [latex]na^{n-1}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-2}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{2}[/latex] [latex]+[/latex] [latex]2a[/latex]. Получим:
[latex]A[/latex] [latex]=[/latex] [latex] \left( \left( na^{n-2}+\left( n-1 \right)a^{n-3}+\ldots+3a+2 \right) \cdot a +1 \right) \cdot a[/latex].
После конечного количества вынесений за скобки, получим:
[latex]A[/latex] [latex]=[/latex] [latex]\left( \left( \ldots \left( \left(na+\left(n-1\right)\right) \cdot a + \left(n-2\right) \right) \ldots+2\right) \cdot a +1\right) \cdot a[/latex].

Таким образом, решение данной задачи сводится к вычислению суммы «изнутри» скобок.

Но из-за того, что в условии подано ограничение только на сумму, программа с реализованным вычислением суммы изнутри и асимптотикой [latex]O \left( n \right)[/latex] не пройдёт все тесты системы www.e-olymp.com в силу частного случая [latex]a = 1[/latex], так как значение [latex]n[/latex] может быть для него достаточно большим, ибо числа [latex]a[/latex] и [latex]n[/latex] компенсируют друг-друга по отношению к максимальному значению суммы. Но в случае [latex]a = 1[/latex] сумма данного ряда является суммой арифметической прогрессии, а именно — натурального ряда. Для вычисления этой суммы существует формула [latex]\sum\limits_{i=1}^{n} {i} = \frac{n \left( n+1 \right)}{2}[/latex]. Этот частный случай легко отсеять.

Асимптотика программы: [latex]const[/latex] при [latex]a = 1[/latex], и [latex]O \left( n \right)[/latex] иначе.

Ссылки

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:

Ю3.22

02/11/2014 by Недомовний Владислав

Задача.

Для заданного [latex]x>1[/latex] вычислить [latex]y=\sqrt{x}[/latex] по итерационной формуле: [latex]y_{i}=\frac{1}{2}(y_{i-1}+\frac{x}{y_{i-1}})[/latex] c заданной погрешностью ε, задав начальное приближение [latex]y_{0}=x[/latex]. Сравнить с результатом использования встроенной функции. Сколько итераций пришлось выполнить?

Тесты.

x	ε	[latex]y_{i}[/latex]	[latex]\left\|\sqrt{x}-y_{i} \right\|[/latex]	i	Комментарий
5	1e-2	2.236069	9.18e-07	4	Пройден
100	1e-1	10.000053	5.29e-05	6	Пройден
100	1e-2	10.000000	1.40e-10	7	Пройден
100	1e-6	10.000000	0.00e+00	8	Пройден
100	1e-10	10.000000	0.00e+00	9	Пройден

Решение.

C++

#include <stdio.h>
#include <math.h>
 
int main()
{
    double x,e; //описание переменных 
    scanf("%lf%lf",&x,&e); //ввод условий
    double y1;
    int i=0;
    double y2=x; //задаем начальное приближение
    do
    {
        y1=y2;
        y2=0.5*(y1+x/y1); //вычисление по заданной формуле
        i=i+1; //подсчет количества итераций
    } while(fabs(y2-y1)>=e);
    printf("%lf\n",y2);
    printf("%e\n",fabs(sqrt(x)-y2)); //сравнение с результатом встроенной функции
    printf("%d",i);
}

#include <stdio.h>

#include <math.h>

int main()

{

double x,e; //описание переменных

scanf("%lf%lf",&x,&e); //ввод условий

double y1;

int i=0;

double y2=x; //задаем начальное приближение

{

y1=y2;

y2=0.5*(y1+x/y1); //вычисление по заданной формуле

i=i+1; //подсчет количества итераций

} while(fabs(y2-y1)>=e);

printf("%lf\n",y2);

printf("%e\n",fabs(sqrt(x)-y2)); //сравнение с результатом встроенной функции

printf("%d",i);

}

Java

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

class Ideone
{
	public static void main (String[] args) 
	{
		double x,e; //описание переменных 
		Scanner sc = new Scanner(System.in);
		x = sc.nextDouble(); //ввод условий
		e = sc.nextDouble();
	    double y1;
	    int i=0;
	    double y2=x; //задаем начальное приближение
	    do
	    {
	        y1=y2;
	        y2=0.5*(y1+x/y1); //вычисление по заданной формуле
	        i=i+1; //подсчет количества итераций
	    } while(Math.abs(y2-y1)>=e);
	    System.out.printf("%f\n",y2);
	    System.out.printf("%e\n",Math.abs(Math.sqrt(x)-y2)); //сравнение с результатом встроенной функции
	    System.out.printf("%d",i);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

double x,e; //описание переменных

Scanner sc = new Scanner(System.in);

x = sc.nextDouble(); //ввод условий

e = sc.nextDouble();

double y1;

int i=0;

double y2=x; //задаем начальное приближение

{

y1=y2;

y2=0.5*(y1+x/y1); //вычисление по заданной формуле

i=i+1; //подсчет количества итераций

} while(Math.abs(y2-y1)>=e);

System.out.printf("%f\n",y2);

System.out.printf("%e\n",Math.abs(Math.sqrt(x)-y2)); //сравнение с результатом встроенной функции

System.out.printf("%d",i);

}

Для подсчета значения квадратного корня для заданного числа создадим цикл. Цикл выполняется пока [latex]\left|y_{i}-y_{i-1}>=\varepsilon\right|[/latex].

С повышением точности растёт количество итераций, но из-за того что, начиная с [latex]\varepsilon=10^{-5}[/latex], погрешность не вычисляется, зависимость оценить нельзя.

Для выполнения программы и проверки тестов можно воспользоваться следующей ссылкой(C++) или другой(Java).

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

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

Tag Archives: итерационная формула

e-olymp 1210. Очень просто!!!

Задача

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

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

Тесты

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

Решение задачи

Ссылки

Related Images:

Ю3.19

Related Images:

Ю3.22

Related Images: