Category Archives: 3. Циклы

Программы, основным элементом которых являются простые циклические вычисления.

Циклы

Опубликовано: 11/10/2014

Циклические, повторяющиеся много раз однотипные вычисления позволяют наилучшим образом продемонстрировать вычислительные возможности компьютеров. Ради этого их изначально и создавали. В задачах этого раздела желательно снова перечитать параграф 5.4 из праймера посвященный «итерационным операторам» (так они назвали семейство из нескольких операторов цикла). Часть 5.4.3 можете пока пропустить, поскольку мы еще не изучали структур данных для которых … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Цифры
Младший бит
Постоянная сумма цифр
Садовник
Большая точность
Дракон
Змей Горыныч
Уровень палиндромности
Нумерация
Битовое представление
Часы
Счастливые билеты
Роботы — сложная задача, предлагается всем желающим
Юный садовод
Максимум
Баксы в банке
Циклические сдвиги
Минимальная сумма цифр
Просто Фибоначчи
Превращение
Увеличить на 2
Двоичные числа
Интересное произведение
Кружок хорового пения
Очень просто!!!
Юные программисты
Коды Грея — только не перемудрите. Если выходит значительно больше 20 строчек кода,
то лучше остановиться и подумать.
Кубики — 3 —
используйте битовые операции для смены предположения о потере кубика для каждой из 52-х букв
Степень симметрии
Сколько можно?
«Зеркально простые» числа
Max — Min

Опубликованные решения

D2574. Сумма ряда

27/02/2017 by Андреев Даниил

Задача

Найти сумму сходящегося ряда: [latex]\sum \limits_{n=1}^{n}\frac{\sin{nx}}{2^{n}}[/latex].

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

[latex]n[/latex] — количество шагов;
[latex]x[/latex] — значение [latex]x[/latex].

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

Сумма ряда [latex]\sum \limits_{n=1}^{n}\frac{sin(nx)}{2^{n}}[/latex].

Тесты

Входные данные		Выходные данные
[latex]n[/latex]	[latex]x[/latex]
10	0.523598	0.651170
25	3.141592	0
15	1.570796	0.399994

Код программы на C++

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    int e=1, n;
    double x, t, o=0;
 
    cin >> n >> x;
 
    for (int j=1; j<(n+1); j++)
    {
        t=sin(j*x);
        e*=2;
        o+=t/e;
    }
 
    cout << fixed << o;
 
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int e=1, n;

double x, t, o=0;

cin >> n >> x;

for (int j=1; j<(n+1); j++)

{

t=sin(j*x);

e*=2;

o+=t/e;

}

cout << fixed << o;

return 0;

}

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

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        int e=1;
        double t, o=0;
        int n = scan.nextInt();
        double x = scan.nextDouble();
        
        for (int j=1; j<(n+1); j++){
            t=Math.sin(j*x);
            e*=2;
            o+=t/e;
        }
        
        System.out.printf("%1$.6f", o);
    }
}

import java.util.*;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

int e=1;

double t, o=0;

int n = scan.nextInt();

double x = scan.nextDouble();

for (int j=1; j<(n+1); j++){

t=Math.sin(j*x);

e*=2;

o+=t/e;

}

System.out.printf("%1$.6f", o);

}

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone на C++;
Ideone на Java;
WolframAlpha.

Related Images:

A320. Вложенный цикл

25/12/2016 by Андреев Даниил

Задача

Вычислить [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

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

Произвольные [latex]n[/latex] и [latex]m.[/latex]

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

Значение [latex]\sum\limits_{k=1}^{n}\left( k^{3}\sum\limits_{l=1}^{m}\left(k-l\right)^{2}\right).[/latex]

Тесты

Входные данные		Выходные данные
[latex]n[/latex]	[latex]m[/latex]
10	15	983455
2	5	150
3	6	816

Код программы на C++

#include <iostream>
using namespace std;
int main()
{
    long double sum_1=0, sum_2=0;
    int n, m;
    cin >> n >> m;
    for(int k=1;k<=n;k++)
    {
        for(int l=1;l<=m;l++)
        {
            sum_2+=(k-l)*(k-l);
        }
        sum_1+=k*k*k*sum_2;
        sum_2-=sum_2;
    }
    cout << sum_1;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

long double sum_1=0, sum_2=0;

int n, m;

cin >> n >> m;

for(int k=1;k<=n;k++)

{

for(int l=1;l<=m;l++)

{

sum_2+=(k-l)*(k-l);

}

sum_1+=k*k*k*sum_2;

sum_2-=sum_2;

}

cout << sum_1;

return 0;

}

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

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        double sum_1=0, sum_2=0;
        int n = scan.nextInt();
        int m = scan.nextInt();
        
        for(int k=1; k<=n; k++){
            for(int l=1; l<=m; l++)  sum_2+=(k-l)*(k-l);
            sum_1+=k*k*k*sum_2;
            sum_2-=sum_2;
        }
        
        System.out.print(sum_1);
    }
}

import java.util.*;

class Main

{

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

{

Scanner scan = new Scanner(System.in);

double sum_1=0, sum_2=0;

int n = scan.nextInt();

int m = scan.nextInt();

for(int k=1; k<=n; k++){

for(int l=1; l<=m; l++) sum_2+=(k-l)*(k-l);

sum_1+=k*k*k*sum_2;

sum_2-=sum_2;

}

System.out.print(sum_1);

}

Решение

Проверим решение с WolframAlpha.

Ссылки

Ideone C++;
Ideone Java;
WolframAlpha.

Related Images:

A322. Максимальная сумма делителей

17/12/2016 by Валентина Андриеш

Задача. Найти натуральное число с максимальной суммой делителей на заданном промежутке.

Входные данные:
— [latex]n[/latex] — промежуток чисел(от 1 до [latex]n[/latex]);

Выходные данные:
— [latex]max[/latex] _ [latex]sum[/latex] — максимальная сумма делителей числа на этом промежутке;
— [latex]max[/latex] _ [latex]number[/latex] — натуральное число с этой суммой;

Тесты:

[latex]n[/latex]	[latex]max[/latex] _ [latex]number[/latex]	[latex]max[/latex] _ [latex]sum[/latex]
100	96	252
8743	8400	30752
23000	22680	87120

Код на языке C++:

#include <iostream>
#include <cmath>
using namespace std;
 
int sum_dividers(int n){
    int sum=0;
    for(int i=1; i<sqrt(n); i++){
        if((n%i)==0)sum+=i+(n/i);
    }
    int i=sqrt(n);
    if(i*i==n)sum+=i;
    return sum;
}
 
int main() {
    int n;
    cin>>n;
    int max_sum=0;
    int max_number=0;
    int j;
    for(j=1; j<=n; j++){
        int s=sum_dividers(j);
        if(max_sum<s){
            max_sum=s;
            max_number=j;
        }
    }
    cout<<max_number<<" "<<max_sum;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int sum_dividers(int n){

int sum=0;

for(int i=1; i<sqrt(n); i++){

if((n%i)==0)sum+=i+(n/i);

}

int i=sqrt(n);

if(i*i==n)sum+=i;

return sum;

}

int main() {

int n;

cin>>n;

int max_sum=0;

int max_number=0;

int j;

for(j=1; j<=n; j++){

int s=sum_dividers(j);

if(max_sum<s){

max_sum=s;

max_number=j;

}

cout<<max_number<<" "<<max_sum;

return 0;

}

Код на языке Java:

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

class Ideone
{
    static int sum_dividers(int n){
        int sum=0;
            for(int i=1; i<Math.sqrt(n); i++){
                    if((n%i)==0)sum+=i+(n/i);
            }
            double i=Math.round(Math.sqrt(n));
            if(i*i==n)sum+=i;
            return sum;
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int max_sum=0;
        int max_number=0;
        int j;
        for(j=1; j<=n; j++){
            int s=sum_dividers(j);
            if(max_sum<s){
                        max_sum=s;
                        max_number=j;
            }
        }
        System.out.println(max_number+" "+max_sum);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

static int sum_dividers(int n){

int sum=0;

for(int i=1; i<Math.sqrt(n); i++){

if((n%i)==0)sum+=i+(n/i);

}

double i=Math.round(Math.sqrt(n));

if(i*i==n)sum+=i;

return sum;

}

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

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

int max_sum=0;

int max_number=0;

int j;

for(j=1; j<=n; j++){

int s=sum_dividers(j);

if(max_sum<s){

max_sum=s;

max_number=j;

}

System.out.println(max_number+" "+max_sum);

}

Решение задачи:
Для нахождения суммы делителей используется функция [latex]sum[/latex] _ [latex]dividers[/latex], которая в созданном цикле сначала находит все делители числа, а после суммирует их, присваивая значение переменной [latex]sum[/latex]. Создав в главной функции [latex]main[/latex] еще один цикл со счетчиком от 1 до [latex]n[/latex], подставляю в предыдущую функцию [latex]sum[/latex] _ [latex]dividers[/latex] все натуральные числа на выбранном промежутке. C помощью свободных переменных [latex]max[/latex] _ [latex]sum[/latex] и [latex]max[/latex] _ [latex]number[/latex] нахожу максимальное значение сумм и соответствующее ему натуральное число.

Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 322

Related Images:

Площадь поверхности

11/12/2016 by Тимур Фирсов

Задача

Найти площадь поверхности, которая является трёхмерным графиком функции [latex]f\left( x, y\right)[/latex], в пределах от [latex]a[/latex] до [latex]b[/latex] по оси [latex]x[/latex] и от [latex]c[/latex] до [latex]d[/latex] по оси [latex]y[/latex] c величиной шага [latex]h[/latex].

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

Четыре целых числа: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex].
Вещественное число: [latex]h[/latex].

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

Площадь поверхности [latex]S[/latex].

Тесты

№	[latex]f\left( x, y\right)[/latex]	Входные данные					Выходные данные
		[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]h[/latex]	[latex]S[/latex]
1	[latex]x+y[/latex]	-10	10	-10	10	0.001	692.82
2	[latex]\left\| x \right\| +\left\| y \right\|[/latex]	-2	2	-2	2	0.005	27.7128
3	[latex]1[/latex]	0	100	0	100	0.1	10000
4	[latex]{x}^{2}+{y}^{2}[/latex]	-1	1	-1	1	0.0005	7.44626

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

#include <iostream>
#include <cmath>
using namespace std;
double z(double x, double y){
    return abs(x)+abs(y);//<-- место для ввода функции z=f(x, y).
}
double dl(double x, double y, double z){
    return sqrt(x*x+y*y+z*z);//Длина вектора.
}
double ras(double xi, double xj, double yi, double yj){
    double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0;
    zii=z(xi, yi); //Найдём координату z каждой вершины треугольников.
    zjj=z(xj, yj);
    zij=z(xi, yj);
    zji=z(xj, yi);
    v1x=(yi-yj)*(zji-zii);  //Вычислим векторное произведение векторов.
    v1y=(zii-zij)*(xj-xi);
    v1z=(yj-yi)*(xj-xi);
    v2x=(yj-yi)*(zji-zjj);
    v2y=(zjj-zij)*(xi-xj);
    v2z=(yi-yj)*(xi-xj);
    return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.
}

int main(){
    double xi, xj, yi, yj, s=0, h;
    int a, b, c, d;
    cin >> a >> b >> c >> d >> h;
    xi = a;
    while(xi<=(b-h)){
        yi=c;
        xj=xi+h;
        while(yi<(d-h)){
            yj=yi+h;
            s+=ras(xi,xj,yi,yj);
            yi=yj;
        }
        xi=xj;
    }
    cout<<s;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double z(double x, double y){

return abs(x)+abs(y);//<-- место для ввода функции z=f(x, y).

}

double dl(double x, double y, double z){

return sqrt(x*x+y*y+z*z);//Длина вектора.

}

double ras(double xi, double xj, double yi, double yj){

double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0;

zii=z(xi, yi); //Найдём координату z каждой вершины треугольников.

zjj=z(xj, yj);

zij=z(xi, yj);

zji=z(xj, yi);

v1x=(yi-yj)*(zji-zii); //Вычислим векторное произведение векторов.

v1y=(zii-zij)*(xj-xi);

v1z=(yj-yi)*(xj-xi);

v2x=(yj-yi)*(zji-zjj);

v2y=(zjj-zij)*(xi-xj);

v2z=(yi-yj)*(xi-xj);

return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.

}

int main(){

double xi, xj, yi, yj, s=0, h;

int a, b, c, d;

cin >> a >> b >> c >> d >> h;

xi = a;

while(xi<=(b-h)){

yi=c;

xj=xi+h;

while(yi<(d-h)){

yj=yi+h;

s+=ras(xi,xj,yi,yj);

yi=yj;

}

xi=xj;

}

cout<<s;

return 0;

}

Решение

Представим поверхность в виде множества геометрических фигур. Тогда её площадь будет суммой площадей этих фигур. В качестве фигур, покрывающих данную поверхность, возьмём треугольники, поскольку через любые [latex]3[/latex] точки в пространстве можно провести плоскость и только одну (а значит и треугольник). Координатную плоскость [latex]xy[/latex] условно поделим на квадраты, где сторона квадрата будет равняться заданному шагу [latex]h[/latex]. Будем рассматривать только квадраты, что лежат в заданных пределах. Условно проведём одну из диагоналей у каждого квадрата — получим треугольники на плоскости. Поочередно будем искать координату [latex]z[/latex] вершин каждой пары треугольников, подставляя уже известные координаты [latex]x[/latex] и [latex]y[/latex] в указанную формулу. Зная координаты треугольников в пространстве, найдём площадь каждого, сумма данных площадей и будет площадью поверхности. Чтоб найти площадь треугольника, зная координаты его вершин, найдем векторное произведение его координат. Возьмем треугольник с координатами вершин [latex]\left( x_i,y_i,z_{ii} \right) [/latex], [latex]\left( x_i, y_j, z_{ij} \right) [/latex] и [latex]\left( x_j, y_i, z_{ji} \right) [/latex], возьмём произвольные два вектора, которые образуют данный треугольник — [latex]\overrightarrow { a } =\left ( x_i-x_i, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, y_i-y_i, z_{ji}-z_{ii} \right)[/latex].
[latex]\overrightarrow { a } =\left ( 0, y_j-y_i, z_{ij}-z_{ii} \right)[/latex], [latex]\overrightarrow { b } =\left ( x_j-x_i, 0, z_{ji}-z_{ii} \right)[/latex].
Тогда векторное произведение [latex]\left [ \overrightarrow { a }, \overrightarrow { b } \right] =\left ( (y_i-y_j)( z_{ji}-z_{ii}), (z_{ii}-z_{ij})(z_{ji}-z_{ii} ), ( y_j-y_i)(x_j-x_i) \right)[/latex].
Поскольку длина вектора равного векторному произведения двух векторов в пространстве равна площади параллелограмма, образованного исходными векторами — найдём его длину и разделим пополам, чтоб получить площадь треугольника, образованного исходными векторами. Значит площадь каждого треугольника можно вычислить по формуле:
[latex]s =\frac { 1 }{ 2 } \sqrt{({(y_i-y_j)}^{2}{( z_{ji}-z_{ii})}^{2}+{(z_{ii}-z_{ij})}^{2}{(z_{ji}-z_{ii} )}^{2}+{( y_j-y_i)}^{2}{(x_j-x_i)}^{2})}[/latex] Тогда площадь поверхности в пределах заданных точек можно вычислить, сложив площади этих треугольников.

Модификация

Модифицируем данную программу для нахождения приблизительной площади поверхности, заданной функцией с корнем чётной степени.

Тесты

№	[latex]f\left( x, y\right)[/latex]	[latex]z_0[/latex]	Входные данные					Выходные данные
			[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]h[/latex]	[latex]S[/latex]
1	[latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]1[/latex]	-1	1	-1	1	0.00011	6.28734
2	[latex]\sqrt { 1-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]7y[/latex]	-1	1	-1	1	0.00011	23.0803
3	[latex]\sqrt { 1-{ x }^{ 2 }-\frac{ { y }^{ 2 }}{ 2 } }[/latex]	[latex]0[/latex]	-1	1	-2	2	0.00015	8.08214
4	[latex]\sqrt { 2-{ x }^{ 2 }-{ y }^{ 2 } }[/latex]	[latex]-1[/latex]	-2	2	-2	2	0.0005	12.5835

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

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

double z(double x,  double y,  double &z0){
    z0=7*y; //<-- место для ввода слагаемых функции f(x, y) не под корнем чётной степени.
    return (1-x*x-y*y)<0? z0:sqrt(1-x*x-y*y)+z0;//<-- место для ввода функции z=f(x, y).
}
long double  dl(double x,  double y,  double z){
    return sqrt(x*x+y*y+z*z);//Длина вектора.
}
double ras(double xi,  double xj,  double yi,  double yj){
    double zii,  zjj,  zij,  zji,  v1x=0,  v1y=0,  v1z=0,  v2x=0,  v2y=0,  v2z=0,  z0=0;
    zii=z(xi,  yi,  z0); //Найдём координату z каждой вершины треугольников.
    zjj=z(xj,  yj,  z0);
    zij=z(xi,  yj,  z0);
    zji=z(xj,  yi,  z0);
    if(z(xi,  yi,  z0)!=z0||z(xi,  yj,  z0)!=z0||z(xj,  yi,  z0)!=z0){//Используем функцию z(),  потому что z0 может оказаться переменной.
        v1x=(yj-yi)*(zji-zii);  //Вычислим векторное произведение векторов.
        v1y=(zij-zii)*(xj-xi);
        v1z=(yi-yj)*(xj-xi);
    }
    if(z(xj,  yj,  z0)!=z0||z(xi,  yj,  z0)!=z0||z(xj,  yi,  z0)!=z0){
        v2x=(yi-yj)*(zji-zjj);
        v2y=(zij-zjj)*(xi-xj);
        v2z=(yj-yi)*(xi-xj);
    }
    return (dl(v1x,  v1y,  v1z)+dl(v2x,  v2y,  v2z))/2;//Найдём площадь треугольников.
}

int main(){
    double xi,  xj,  yi,  yj,  s=0,  h,  z0=0;
    int a,  b,  c,  d;
    cin >> a >> b >> c >> d >> h;
    xi = a;
    while(xi<=(b-h)){
        yi=c;
        xj=xi+h;
        while(yi<=(d-h)){
            yj=yi+h;
            s+=ras(xi, xj, yi, yj);
            yi=yj;
        }
        xi=xj;
    }
    cout<<s;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double z(double x, double y, double &z0){

z0=7*y; //<-- место для ввода слагаемых функции f(x, y) не под корнем чётной степени.

return (1-x*x-y*y)<0? z0:sqrt(1-x*x-y*y)+z0;//<-- место для ввода функции z=f(x, y).

}

long double dl(double x, double y, double z){

return sqrt(x*x+y*y+z*z);//Длина вектора.

}

double ras(double xi, double xj, double yi, double yj){

double zii, zjj, zij, zji, v1x=0, v1y=0, v1z=0, v2x=0, v2y=0, v2z=0, z0=0;

zii=z(xi, yi, z0); //Найдём координату z каждой вершины треугольников.

zjj=z(xj, yj, z0);

zij=z(xi, yj, z0);

zji=z(xj, yi, z0);

if(z(xi, yi, z0)!=z0||z(xi, yj, z0)!=z0||z(xj, yi, z0)!=z0){//Используем функцию z(), потому что z0 может оказаться переменной.

v1x=(yj-yi)*(zji-zii); //Вычислим векторное произведение векторов.

v1y=(zij-zii)*(xj-xi);

v1z=(yi-yj)*(xj-xi);

}

if(z(xj, yj, z0)!=z0||z(xi, yj, z0)!=z0||z(xj, yi, z0)!=z0){

v2x=(yi-yj)*(zji-zjj);

v2y=(zij-zjj)*(xi-xj);

v2z=(yj-yi)*(xi-xj);

}

return (dl(v1x, v1y, v1z)+dl(v2x, v2y, v2z))/2;//Найдём площадь треугольников.

}

int main(){

double xi, xj, yi, yj, s=0, h, z0=0;

int a, b, c, d;

cin >> a >> b >> c >> d >> h;

xi = a;

while(xi<=(b-h)){

yi=c;

xj=xi+h;

while(yi<=(d-h)){

yj=yi+h;

s+=ras(xi, xj, yi, yj);

yi=yj;

}

xi=xj;

}

cout<<s;

return 0;

}

Условно отделим от функцию [latex]f\left( x, y\right)[/latex] слагаемые, что не под корнем, если такие имеются. Тогда [latex]z_0[/latex] равно части функции, что не под корнем. Для того, чтоб рассматривать площади треугольников, вершины которых выходят за область определения функции, доопределим их в [latex]z_0[/latex] по оси [latex]z[/latex]. Затем вычислим площадь треугольников, у которых как минимум одна вершина не лежит на [latex]z=z_0[/latex] .

Ссылки

Related Images:

D2631. Сумма ряда с заданной точностью

08/12/2016 by Тимур Фирсов

Задача

Найти количество членов ряда, требуемых для получения значения [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] с точностью до [latex]\varepsilon [/latex], а также найти само значение суммы с заданной точностью.

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

Точность [latex]\varepsilon [/latex].

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

Количество членов ряда [latex]n[/latex].
Значение суммы [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex].

Тесты

№	Входные данные	Выходные данные
	[latex]\varepsilon[/latex]	[latex]n[/latex]	[latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex]
1	0.01	98	4.74785
2	1e-7	4188	5.71199
3	1e-9	8900	5.71208
4	1	1	0.367879

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

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

int main() {
    double sum=0, xn=1, eps;
    int n=0;
    cin >> eps;
    while(xn>=eps){
        n++;
        xn=pow(M_E, -pow(n,1.0/3));
        sum+=xn;
    }
    cout << n << " " << sum;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double sum=0, xn=1, eps;

int n=0;

cin >> eps;

while(xn>=eps){

n++;

xn=pow(M_E, -pow(n,1.0/3));

sum+=xn;

}

cout << n << " " << sum;

return 0;

}

Решение

Докажем, что ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] сходится. Обозначим общий член данного ряда [latex]x_n[/latex]. Поскольку все члены ряда положительны, воспользуемся предельным признаком сравнения рядов. Для сравнения возьмём сходящийся ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ \frac { 1 }{ { n }^{ 2 } } } [/latex], общий член которого обозначим [latex]b_n[/latex]: [latex]\lim\limits_{ n\rightarrow \infty }{ \frac { x_n }{ b_n } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ n }^{ 2 } }=K[/latex], тогда данный ряд сходится, если [latex]0<K<\infty [/latex], либо [latex]K=0[/latex].
[latex]\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ n }^{ 2 } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n } }{ e }^{ {2}{\ln { \left( n \right)} } } }=\lim\limits_{ n\rightarrow \infty }{ { e }^{ -\sqrt [ 3 ]{ n }+{ {2}{\ln { \left( n \right)} } } }}={ e }^{ -\infty }=0 [/latex].
[latex]K=0[/latex], а значит ряд [latex]\sum\limits_{ n=1 }^{ \infty }{ { e }^{ -\sqrt [ 3 ]{ n } } } [/latex] сходится и значение суммы является конечным числом. Тогда для сколь угодно малого [latex]\varepsilon >0[/latex] найдётся номер, начиная с которого каждый последующий член ряда меньше [latex]\varepsilon[/latex]

Ссылки

Код программы.
Условие задачи (страница 257).

Related Images:

A333. Наибольший общий делитель чисел последовательности

29/11/2016 by Вадим Гордийчук

Примечание: [latex]GCD[/latex] — Greatest common divisor (Наибольший общий делитель, НОД).

Задача

Даны натуральные числа [latex]m[/latex], [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex] [latex]m \ge 2[/latex]. Вычислить [latex]GCD \left( n, \ldots, n_m \right)[/latex], воспользовавшись для этого соотношением [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left( k = 3, \ldots, n \right)[/latex] и алгоритмом Евклида.

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

Количество чисел [latex]m[/latex]; числа [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex].

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

[latex]GCD \left( n_1, \ldots, n_m \right)[/latex].

Тесты

Входные данные					Выходные данные
2	3	4			1
2	4	8			4
4	24	23	40	90	1
4	36	48	20	24	4
3	30	738	1926		6

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

#include <iostream>
using namespace std;

unsigned long long gcd(unsigned long long m, unsigned long long n)
{
    return (n != 0) ? gcd(n, m%n) : m;
}

int main()
{
    unsigned long long m, n, result;
    cin >> m >> result;
    for (unsigned long long i = 2; i <= m; i++)
    {
        cin >> n;
        result = gcd(result, n);
        if (result == 1) m = 1; //same as break
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

using namespace std;

unsigned long long gcd(unsigned long long m, unsigned long long n)

{

return (n != 0) ? gcd(n, m%n) : m;

}

int main()

{

unsigned long long m, n, result;

cin >> m >> result;

for (unsigned long long i = 2; i <= m; i++)

{

cin >> n;

result = gcd(result, n);

if (result == 1) m = 1; //same as break

}

cout << result << endl;

return 0;

}

import java.util.*;

public class Main
{
    public static long gcd(long m, long n)
    {
        if (n != 0)
            return gcd(n, m%n);
        else
            return m;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long m = in.nextLong(), n, result = in.nextLong();
        
        for(long i = 2; i <= m; ++i)
        {
            n = in.nextLong();
            result = gcd(result, n);
            if (result == 1) m = 1; //same as break
        }
        System.out.println(result);
    }
}

import java.util.*;

public class Main

{

public static long gcd(long m, long n)

{

if (n != 0)

return gcd(n, m%n);

else

return m;

}

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

{

Scanner in = new Scanner(System.in);

long m = in.nextLong(), n, result = in.nextLong();

for(long i = 2; i <= m; ++i)

{

n = in.nextLong();

result = gcd(result, n);

if (result == 1) m = 1; //same as break

}

System.out.println(result);

}

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

Для решения данной задачи необходимо использовать данную в условии формулу [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left(\right)[/latex].
Также необходимо воспользоваться алгоритмом Евклида для реализации рекурсивной функции [latex]GCD[/latex]:
Пусть [latex]m[/latex] и [latex]n[/latex] — одновременно не равные нулю целые неотрицательные числа и пусть [latex]m \ge n[/latex]. Тогда если [latex]n=0[/latex], то [latex]GCD\left(n, m\right)=m[/latex], а если [latex]n\ne0[/latex], то для чисел [latex]m[/latex], [latex]n[/latex] и [latex]r[/latex], где [latex]r[/latex] — остаток от деления [latex]m[/latex] на [latex]n[/latex], выполняется равенство [latex]GCD\left(m, n\right)=GCD\left(n, r\right)[/latex]. (задача 89 задачника С. Абрамова)
Программа записывает в переменную m число [latex]m[/latex], а в result — [latex]n_1[/latex].
Затем, используя формулу [latex]\left(\right)[/latex], программа до окончания цикла считывает следующие числа из последовательности поверх предыдущих в переменную n и находит сперва [latex]GCD\left(n_1, n_2\right)=x_1[/latex], [latex]GCD\left(x_1, n_3 \right)=x_2[/latex], затем [latex]GCD\left(x_2, n_4\right)=x_3[/latex] и так далее, вплоть до нахождения [latex]GCD[/latex] всех чисел, постоянно записывая новые [latex]GCD[/latex] поверх старых в переменную result. В итоге, программа выводит результирующий [latex]GCD[/latex], который и является ответом.

Ссылки

Related Images:

Ровно 20 простых делителей

28/11/2016 by Мазурок Игорь Евгеньевич

Задача. За 2 секунды проверить предположение о том, что у некоторого числа [latex]n \le 10^{18}[/latex] имеется ровно 20 простых делителей.
Попытаться решить задачу и проверить своё решение можно здесь.

Тесты

Вход	Выход	Примечание
10000000000	Yes	[latex]2^{10}\cdot 5^{10}[/latex]
1048576	Yes	[latex]2^{20}[/latex]
999999999987679232	Yes	[latex]2^19 \cdot 1907348632789[/latex]
2	No	[latex]2^{1}[/latex]
1000000000000000003	No	Простое число. Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
1000000000012845056	Yes	[latex]2^{19}\cdot 1907348632837[/latex] Немного выходит за пределы ограничения задачи, но допустимо для типов unsigned long long
99999989699999923	No	[latex]99999989 \cdot 1000000007[/latex]
8388608	No	[latex]2^{23}[/latex] — слишком много делителей

Решение

Идея решения состоит в попытках деления исходного числа [latex]n[/latex] на последовательно увеличивающиеся целые числа [latex]d,[/latex] начиная с двойки. Если удается произвести деление без остатка, то очередной делитель найден. Исходное число можно разделить на этот делитель и в дальнейшем искать делители полученного частного, т.е. [latex]n \leftarrow \frac{n}{d}.[/latex] Теперь нам остается найти на один делитель меньше. Такая процедура должна будет успешно завершиться ровно 19 раз. Частное от последнего 19-го деления должно оказаться простым числом — тогда простых делителей окажется ровно 20.
При подготовке тестов выяснилось, что трудности могут вызывать следующие ситуации:

No — отрицательный вердикт: слишком мало делителей. В худшем случае одно большое простое число.
Yes — положительный вердикт: 19 небольших делителей и большой 20-й. В худшем случае рассматривается число [latex]2^{19} \cdot 1907348632789 = 999999999987679232[/latex]

В обоих случаях трудности вызывает поиск делителей довольно большого простого числа. Необходимо аккуратно ограничить диапазон поиска возможных делителей так, чтобы не выполнять излишней работы, но и не пропустить делителей.
Зададимся вопросом, как долго нам придётся перебирать возможные делители (начиная с числа 2) пока не встретим первый (наименьший) делитель?
Рассмотрим первый случай (слишком мало делителей). Пусть нам известно, что число имеет [latex]m[/latex] делителей. Первый, встретившийся нам делитель (т.е. наименьший) должен быть таким, чтобы [latex]d^{m} \le n, [/latex] т.е. [latex]d \le n^{\frac{1}{m}} = \sqrt[m]{n}.[/latex] Это очень хорошее ограничение, т.к. в первом случае нам придется перебирать возможные делители до [latex]\left( 10^{18} \right)^{\frac{1}{20}} = 10^{\frac{18}{20}} \le 7.[/latex] Это совсем немного вариантов. Т.е. достаточно проверить деление на 3, 5 и 7 для самого большого возможного [latex]n[/latex]. При правильном выборе границ поиска «страшный» случай огромного простого числа [latex]n[/latex] оказывается очень лёгким.

Границы поиска делителей в худшем случае

Чуть сложнее оказывается ситуация когда есть один маленький делитель (например, 2). Тогда при поиске следующего делителя нам придутся работать с числами [latex]n \le \frac{10^{18}}{2} = 5 \cdot 10^{17}.[/latex] Поскольку теперь останется найти не 20 а только 19 делителей? то ограничение на возможное значение минимального делителя станет таким: [latex]\left( 5 \cdot 10^{17} \right)^{\frac{1}{19}} = \sqrt[19]{5 \cdot 10^{17}} \le 8.[/latex] Что даёт тот же набор возможных простых делителей. Давайте посмотрим, как у нас будут изменяться границы поиска в худшем случае. Т.е. для максимально большого [latex]n[/latex] и делителях равных 2. Рассуждая аналогичным образом можно рассчитать границы поиска остальных делителей в худшем случае:

[latex]m[/latex]	Граница поиска в худшем случае
20	7
19	8
18	9
17	10
16	11
15	12
14	14
13	16
12	19
11	24
10	31
9	42
8	62
7	102
6	198
5	497
4	1976
3	19686
2	1 953 125
1	1 381 067

Как видим значения вполне доступны для полного перебора за 1-2 секунды на обычном персональном компьютере.
Случай с последним делителем будет рассмотрен отдельно далее.

Теперь рассмотрим второй случай. У нас имеется 19 маленьких делителей (в худшем случае это двойки) и одно большое простое число. Насколько большие делители нужно проверить прежде чем заключить, что оставшееся число простое?
Оставшееся после 19 делений на два число не может превышать [latex]\frac{10^{18}}{2^{19}}=0.5 \cdot 5^{18}.[/latex] Если оставшееся число не является простым, то у него должен быть делитель не превышающий квадратного корня из этого числа. Т.е. поиск делителей в этом последнем случае не может продлиться дольше чем до [latex]\sqrt{0.5 \cdot 5^{18}} = 1381067.[/latex]

Код

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

При извлечении корня может быть получено неточное значение. Это связано как с ошибкой округления. Например, при работе с числами типа double [latex]\sqrt[3]{1000000}[/latex] оказывается не 100, как мы ожидаем, а примерно [latex]99.9999999999999716.[/latex] Из-за этого мы можем не найти делитель в точности равный правой границе интервала поиска. Для компенсации возможной ошибки к правой границе была добавлена некоторая небольшая величина. Конкретное значение выбирается на основании пессимистической оценки возможной погрешности.
Верхняя граница поиска делителей не превышает [latex]\sqrt[m]{n}[/latex] если число делителей [latex]m \ge 2.[/latex]. Когда мы хотим убедиться, что последнее [latex]\left(m=1\right)[/latex] оставшееся число является простым, мы ищем его делители до [latex]\sqrt[2]{n}.[/latex]. Т.е. предполагаем, что число не простое и ищем его делители.

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    unsigned long long n, d = 2;
    cin >> n;
    int m = 20;                     // ищем m делителей числа n
    while (m > 0 && d <= pow(n, 1./max(2, m)) + 1e-10) {
        if (n % d == 0) {           // если делитель найден,
            n /= d;                 // то делим
            m--;                    // и ищем на один делитель меньше
        } else d++;                 // иначе проверяем следующее число
    }
    cout << (m == 1? "Yes" : "No"); // найдено m делителей?
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

unsigned long long n, d = 2;

cin >> n;

int m = 20; // ищем m делителей числа n

while (m > 0 && d <= pow(n, 1./max(2, m)) + 1e-10) {

if (n % d == 0) { // если делитель найден,

n /= d; // то делим

m--; // и ищем на один делитель меньше

} else d++; // иначе проверяем следующее число

}

cout << (m == 1? "Yes" : "No"); // найдено m делителей?

return 0;

}

Задание

Существенным недостатком программы является то, что она перебирает в качестве возможных простых делителей все чётные числа. Естественно, ни одно из них (кроме 2) не может оказаться простым делителем и работа выполняется впустую. Можно надеяться существенно уменьшить время работы программы за счёт правильной организации перебора возможных делителей.
Попытайтесь это сделать.

Related Images:

A334(б). Сумма в сумме

22/11/2016 by Роман Саркисян

Условие

Вычислить [latex]\sum\limits _{ i=1 }^{ k }{ \sum\limits _{ j=1 }^{ t }{ \sin { ({ i }^{ 3 }+{ j }^{ 4 }) } } } [/latex] .

Решение

В данной задаче нам необходимо сделать два цикла, а конкретней — цикл в цикле.

Тесты

[latex]k[/latex]	[latex]t[/latex]	[latex]S[/latex]
1	1	0.9092
10	15	1.4908
20	30	8.8956
60	100	41.9133

#include <iostream>
#include <math.h>
using namespace std;
int main() {
    double S=0;
    int k,t;
    cin >>k>>t;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=t;j++){
            S+=sin(i*i*i+j*j*j*j);
        }
    }
    cout << S;
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double S=0;

int k,t;

cin >>k>>t;

for(int i=1;i<=k;i++){

for(int j=1;j<=t;j++){

S+=sin(i*i*i+j*j*j*j);

}

cout << S;

return 0;

}

Воспользуемся веб-приложением и посчитаем сумму ряда.

Ссылки

Задачник Абрамова
Код на ideone

Related Images:

A324. Делители одного числа, взаимно простые с другим

19/11/2016 by Иванна Ялымова

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

[latex]q[/latex]	[latex]p[/latex]	Все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex]
40	15	1 2 4 8
87	3	1 29

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

Код программы на С++

#include <iostream>
using namespace std;
unsigned long gcd(unsigned long x, unsigned long y) {
    return (y!=0) ? gcd(y,x%y) : x;
}

int main() {
    unsigned int q = 0, p;
    cin >> q >> p;
    for (unsigned int i = 1; i <= q; i++) { 
        if((q % i) == 0) {
            if (gcd(i,p) == 1)
                cout << i << " ";
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

unsigned long gcd(unsigned long x, unsigned long y) {

return (y!=0) ? gcd(y,x%y) : x;

}

int main() {

unsigned int q = 0, p;

cin >> q >> p;

for (unsigned int i = 1; i <= q; i++) {

if((q % i) == 0) {

if (gcd(i,p) == 1)

cout << i << " ";

}

return 0;

}

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

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int q = 0, p;
        Scanner in = new Scanner(System.in);
            
        q = in.nextInt();
        p = in.nextInt();
        
        for (int i = 1; i <= q; i++) { 
            if((q % i) == 0) {
                if (gcd(i,p) == 1)
                    System.out.print(i + " ");
            }
        }
    }
    public static long gcd(long x, long y) {
            return (y!=0) ? gcd(y,x%y) : x;
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int q = 0, p;

Scanner in = new Scanner(System.in);

q = in.nextInt();

p = in.nextInt();

for (int i = 1; i <= q; i++) {

if((q % i) == 0) {

if (gcd(i,p) == 1)

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

}

public static long gcd(long x, long y) {

return (y!=0) ? gcd(y,x%y) : x;

}

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть [latex]m[/latex] и [latex]n[/latex] — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для числе [latex]m[/latex], [latex]n[/latex] и [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].
Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. Если найденный наибольший делитель равен 1, то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

Ссылки

Условие задачи
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)

Related Images:

A334(а). Вложенная сумма

16/11/2016 by Антон Куперман

Задача

Вычислить: [latex]\sum \limits_{i=1}^{m}\sum \limits_{j=1}^{n}\frac{1}{i+j^2}[/latex], где [latex]m,n[/latex] — вводимые нами числа.

Тесты

Вход([latex]m,n[/latex])	Выход([latex]S[/latex])
40 20	13.6458
100 50	24.6458
200 25	31.7764
1000 282	89.8078

Код на C++

#include <iostream>
using namespace std;
 
int main() {
    double x, S=0, m, n;
    cin >> m >> n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            x=1.0/(i+j*j);
            S+=x;
        }
    }
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, S=0, m, n;

cin >> m >> n;

for(int i=1;i<=m;i++)

{

for(int j=1;j<=n;j++)

{

x=1.0/(i+j*j);

S+=x;

}

cout << S;

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 S=0, m, n;
        m=in.nextInt();
        n=in.nextInt();
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                S+=1.0/(i+j*j);
            }
        }
        System.out.print(S);
    }
}

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 S=0, m, n;

m=in.nextInt();

n=in.nextInt();

for(int i=1;i<=m;i++){

for(int j=1;j<=n;j++){

S+=1.0/(i+j*j);

}

System.out.print(S);

}

Решение

Вводим два оператор цикла for, один вложенный в другой. Задаем наше выражение, а затем суммируем его, согласно циклу.

Ссылки

Related Images:

A327. Простые числа

13/11/2016 by Эммануил Прокопов

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны натуральные числа [latex]a, b (a\le b)[/latex]. Получить все простые числа [latex]p[/latex], удовлетворяющие неравенствам [latex]a\le p\le b[/latex].

Входные данные:
Два натуральных числа [latex]a[/latex] и [latex]b[/latex].

Выходные данные:
Некоторое количество натуральных чисел.

Тесты.

№	Входные данные		Выходные данные
	[latex]a[/latex]	[latex]b[/latex]	[latex]p[/latex]
1	1	4	2, 3
2	0	1	Not found
3	5	5	5
4	6	20	7, 11, 13, 17, 19

Код программы (C++).

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

int main() {
    cout<<"Primes: ";
    bool prime;
    int a,b;
    cin>>a>>b;
    vector<int> primes;
    for(int e=2; e<=b; e++)
    {
        prime=true;
        for(int i=0; i<primes.size(); i++)
        {
            if((e%primes[i])==0) prime=false;
        }
        if(prime==true)
        {
            primes.push_back(e);
            if(e>=a) cout<<e<<" ";
        }
    }
    if(b<2) cout<<"Not found.";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

cout<<"Primes: ";

bool prime;

int a,b;

cin>>a>>b;

vector<int> primes;

for(int e=2; e<=b; e++)

{

prime=true;

for(int i=0; i<primes.size(); i++)

{

if((e%primes[i])==0) prime=false;

}

if(prime==true)

{

primes.push_back(e);

if(e>=a) cout<<e<<" ";

}

if(b<2) cout<<"Not found.";

return 0;

}

Код программы (Java).

import java.util.*;
import java.math.*;
 
class sieveOfEratosthenes
{
    public void find(int a, int b){
        boolean[] prime = new boolean[b+1];
        Arrays.fill(prime, Boolean.TRUE);
        prime[0] = false;
        prime[1] = false;
        for(int i = 2; i <= b; ++i){
            if(prime[i]){
                for(int j = i*i; j <= b; j += i){
                    prime[j] = false;
                }   
            }   
        }
 
        boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число?
        for(int i = a; i <= b; ++i){
            if(prime[i]){
                System.out.print(i + " ");
                primes_found = true;
            }
        }
        if(!primes_found) System.out.print("Not found");
    }
}
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        int a, b;
        a = in.nextInt();
        b = in.nextInt();
        sieveOfEratosthenes c = new sieveOfEratosthenes();
        c.find(a, b);
    }
}

import java.util.*;

import java.math.*;

class sieveOfEratosthenes

{

public void find(int a, int b){

boolean[] prime = new boolean[b+1];

Arrays.fill(prime, Boolean.TRUE);

prime[0] = false;

prime[1] = false;

for(int i = 2; i <= b; ++i){

if(prime[i]){

for(int j = i*i; j <= b; j += i){

prime[j] = false;

}

boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число?

for(int i = a; i <= b; ++i){

if(prime[i]){

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

primes_found = true;

}

if(!primes_found) System.out.print("Not found");

}

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int a, b;

a = in.nextInt();

b = in.nextInt();

sieveOfEratosthenes c = new sieveOfEratosthenes();

c.find(a, b);

}

Решение.
C++:
Для начала, вводятся два целых числа. Очевидно, что придётся проверять, являются ли простыми числа, большие чем [latex]a[/latex] и меньшие чем [latex]b[/latex]. Не представляется возможным заранее узнать, насколько большими будут эти числа, потому, на мой взгляд, наиболее подходящим решением будет каждый запуск программы заново находить все простые числа до [latex]b[/latex]. Создаётся вектор, в котором они будут храниться (целесообразно использовать именно вектор, поскольку неизвестно точно, сколько чисел придётся хранить). Далее идёт цикл, в котором каждое число от двух до [latex]b[/latex], если оно не делится нацело ни на один из элементов вектора (это проверяется при по мощи вложенного цикла), добавляется в этот вектор и, если оно больше чем [latex]a[/latex], выводится. В случае, если [latex]b<2[/latex], очевидно, простые числа найдены не будут, потому выводится "Not found."
Java:
Решение на Java представляет собой реализацию Решета Эратосфена.
Код на ideone.com: C++, Java.
Условие задачи (с.135)

Related Images:

А329. Квадрат суммы цифр числа

13/11/2016 by Тимур Фирсов

Задача

Задача из сборника задач по программированию Абрамова С.А. 2000 г.
Даны натуральные числа [latex]n[/latex], [latex]m[/latex]. Получить все меньшие [latex]n[/latex] натуральные числа, квадрат суммы цифр которых равен [latex]m[/latex].

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

Два положительных числа [latex]n[/latex] и [latex]m[/latex].

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

Все целые числа из [latex]\left( 0,n \right)[/latex], удовлетворяющие условию.

Тесты

№	Входные данные		Выходные данные
№	[latex]n[/latex]	[latex]m[/latex]
1	1234	9	3 12 21 30 102 111 120 201 210 300 1002 1011 1020 1101 1110 1200
2	100	4	2 11 20
3	49	49	7 16 25 34 43
4	1000	1	1 10 100

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

#include <iostream>
using namespace std;

int main() {
    unsigned n, m, t, sum, i=1;
    cin>>n>>m;
    for(i;i<n;i++){
        t=i;
        sum=0;
        while(t!=0){
            sum+=t%10;
            t/=10;
        }
        if(sum*sum==m)cout<<i<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned n, m, t, sum, i=1;

cin>>n>>m;

for(i;i<n;i++){

t=i;

sum=0;

while(t!=0){

sum+=t%10;

t/=10;

}

if(sum*sum==m)cout<<i<<" ";

}

return 0;

}

Решение

Для того, чтоб найти каждую цифру числа будем искать остаток от деления на [latex]10[/latex], которым является последняя цифра числа, а затем делить число нацело на [latex]10[/latex], чтоб предпоследняя цифра стала последней. Будем повторять эту операцию пока число не равно [latex]0[/latex]. Все полученные цифры числа складываем. Таким способом будем искать сумму цифр каждого целого числа от [latex]1[/latex] до [latex]n-1[/latex], параллельно возводя полученную сумму в квадрат, а результат сравнивая с [latex]m[/latex].

Ссылки

Код программы.
Условие задачи (страница 135).

Related Images:

D2575. Сумма ряда

30/10/2016 by Валентина Андриеш

Условие задачи:
Найти сумму сходящегося ряда: [latex]\frac{\cos x-\cos 2x}{1}+\frac{\cos 2x -\cos 3x}{2}+\cdots+\frac{\cos nx-\cos(n+1)x}{n}+\cdots[/latex]

Входные данные:
[latex]x[/latex] — константа;
[latex]number[/latex] — номер искомой частичной суммы;

Выходные данные:
[latex]value[/latex] — значения необходимых слагаемых;
[latex]partial[/latex] _ [latex]amount[/latex] — искомая частичная сумма;

Тесты:

[latex]x[/latex]	[latex]number[/latex]	[latex]value[/latex]	[latex]partial[/latex] _ [latex]amount[/latex]
10	3	-1.24715 0.126915 0.27373	-0.846508
100	4	0.375131 0.254642 0.167733 0.0896382	0.887145
5	5	1.12273 -0.0396918 -0.389257 -0.14578 0.16739	0.715395

Код на языке C++:

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

int main() {
    int number;
    double x;
    cin>>x>>number;
    double value;
    double partial_amount=0;
    int n=1;
    while(n<=number){
        value=(cos((n*x))-cos(((n+1)*x)))/n;
        cout<<value<<" ";
        partial_amount+=value;
        n++;
    }
    cout<<endl;
    cout<<partial_amount;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int number;

double x;

cin>>x>>number;

double value;

double partial_amount=0;

int n=1;

while(n<=number){

value=(cos((n*x))-cos(((n+1)*x)))/n;

cout<<value<<" ";

partial_amount+=value;

n++;

}

cout<<endl;

cout<<partial_amount;

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);
        int number=in.nextInt();
        double x=in.nextDouble();
        double value;
        double partial_amount=0;
        int n=1;
        while(n<=number){
            value=(Math.cos((n*x))-Math.cos(((n+1)*x)))/n;
            System.out.println(value + " " );
            partial_amount+=value;
            n++;
        }
        System.out.println("\n"+partial_amount);
    }
}

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);

int number=in.nextInt();

double x=in.nextDouble();

double value;

double partial_amount=0;

int n=1;

while(n<=number){

value=(Math.cos((n*x))-Math.cos(((n+1)*x)))/n;

System.out.println(value + " " );

partial_amount+=value;

n++;

}

System.out.println("\n"+partial_amount);

}

Решение задачи:
Под словом «ряд» в математическом анализе понимают сумму бесконечного числа слагаемых. Зададим цикл с счетчиком [latex]n[/latex] от 1 до заданного пользователем числа [latex]number[/latex]. Именно такое количество необходимых слагаемых [latex]value=\frac{\cos nx -\cos (n+1)x}{n}[/latex] будет найдено на каждом шаге цикла для последующего суммирования и нахождения искомой частичной суммы.

Код задачи на C++: Ideone
Код задачи на Java: Ideone

Related Images:

D2548. Сходимость и сумма ряда

27/10/2016 by Роман Саркисян

Условие

Доказать сходимость ряда и найти его сумму
[latex]\frac { 1 }{ 2 } + \frac { 3 }{ 4 } + \frac { 5 }{ 8 } + \ldots + \frac { 2n-1 }{ { 2 }^{ n } } + \ldots [/latex]

Решение

Для начала докажем, что наш ряд сходится. Докажем это, через признак Даламбера. Суть этого признака заключается в том, что если предел отношения последующего члена к предыдущему меньше [latex]1[/latex](или в частных случаях равен [latex]0[/latex]) то данный ряд будет сходится.
Берем отношение последующего и предыдущего [latex]\lim\limits_{ n\to \infty } \frac { \frac{ 2(n+1)-1 }{ { 2 }^{ n+1 } } }{ \frac{ 2n-1 }{ { 2 }^{ n } } }[/latex] превратим нашу 4-х этажную дробь в 2-х этажную [latex]\lim\limits _{ n\to \infty } \frac { ({ 2(n+1)-1){ 2 }^{ n } } }{ { (2n-1 }){ 2 }^{ n+1 } }[/latex] раскроем скобки и применим свойство степеней, получим [latex] \lim\limits _{ n\to \infty } \frac { (2n+2-1){ 2 }^{ n } }{ (2n-1){ 2 }^{ n }2 }[/latex] далее приведем подобные сократим дробь и снова раскроим скобки, получим [latex]\lim\limits _{ n\to \infty } \frac { 2n+1 }{ 4n-2 } [/latex] далее чтобы перейти непосредственно к пределу разделим коэффициенты при старших степенях числителя на знаменатель, в ответе получаем [latex]\frac { 2 }{ 4 }[/latex] [latex]=[/latex] [latex]\frac { 1 }{ 2 }[/latex].
[latex]\frac { 1 }{ 2 }[/latex] [latex]<[/latex] [latex]1[/latex] из этого следует что данный ряд сходится!
Далее найдем сумму это ряда. [latex]\sum\limits_{ n=1 }^{ \infty } { \frac { 2n-1 }{ { 2 }^{ n } } }[/latex] Воспользуемся веб-приложением и посчитаем сумму ряда.

Тесты

[latex]n[/latex]	сумма [latex]n[/latex] элементов
1	0.5
2	1.25
3	1.875
23	2.99999
24	3

#include <iostream>
using namespace std;
int main() {
    int a,n;
    double s=0,q=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        q=q*2;  
        s+=(2*i-1)/q;
    }
    cout<<s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a,n;

double s=0,q=1;

cin>>n;

for(int i=1;i<=n;i++){

q=q*2;

s+=(2*i-1)/q;

}

cout<<s;

return 0;

}

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

class Ideone
{
  public static void main (String[] args) throws java.lang.Exception
  {
    int a,n;
    double s=0,q=1;
    Scanner in = new Scanner(System.in);
    n=in.nextInt();
    for(int i=1;i<=n;i++){
      q=q*2;  
      s+=(2*i-1)/q;
    }
    System.out.println(s);

  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int a,n;

double s=0,q=1;

Scanner in = new Scanner(System.in);

n=in.nextInt();

for(int i=1;i<=n;i++){

q=q*2;

s+=(2*i-1)/q;

}

System.out.println(s);

}

Код на ideone C++
Код на ideone Java

Related Images:

D2580. Сходимость ряда

24/10/2016 by Иванна Ялымова

Задача. Пользуясь признаками сравнения, Даламбера или Коши, исследовать сходимость ряда: [latex]\frac{1!}{1}+\frac{2!}{2^2}+\frac{3!}{3^3}+\ldots+\frac{n!}{n^n}+\ldots[/latex]

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

[latex]n[/latex] — количество взятых членов ряда.

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

[latex]sum[/latex] — сумма.

Тесты

Входные данные	Выходные данные
1	Сумма: 1 Числитель: 1 Знаменатель: 1
3	Сумма: 1.72222 Числитель: 6 Знаменатель: 9
20	Сумма: 1.87985 Числитель: 2.4329e+18 Знаменатель: 5.24288e+24

Код на C++

#include <iostream>
using namespace std;
long double pow(long double number, unsigned int power) {
    long double answer = 1;
    for (int i = 0; i < power; i++){
        answer *= number;
    }
    return answer;
}
int main() {
    long double sum = 0; unsigned int n = 0; long double numerator = 1, denominator = 1;
    //numerator - числитель, denominator - знаменатель, sum - сумма.
    cin >> n;
    for (unsigned int i = 1; i <= n; i++) {
        denominator = pow(i, i-1);
        sum += (1.0*numerator)/denominator; 
        numerator*=i;
    }
    cout << "Сумма: " << sum << endl;
    cout << "Числитель: " << numerator << endl;
    cout << "Знаменатель: " << denominator << endl;
    return 0;
}

#include <iostream>

using namespace std;

long double pow(long double number, unsigned int power) {

long double answer = 1;

for (int i = 0; i < power; i++){

answer *= number;

}

return answer;

}

int main() {

long double sum = 0; unsigned int n = 0; long double numerator = 1, denominator = 1;

//numerator - числитель, denominator - знаменатель, sum - сумма.

cin >> n;

for (unsigned int i = 1; i <= n; i++) {

denominator = pow(i, i-1);

sum += (1.0*numerator)/denominator;

numerator*=i;

}

cout << "Сумма: " << sum << endl;

cout << "Числитель: " << numerator << endl;

cout << "Знаменатель: " << denominator << endl;

return 0;

}

Код на Java

import java.io.PrintWriter;
import java.util.Scanner;

public class A {

    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        double sum = 0;
        double numerator = 1, denominator = 1;
        int n = in.nextInt();

        for (int i = 1; i <= n; i++)
        {
            denominator = pow(i,i-1);
            sum += (1.0*numerator)/denominator;
            numerator*=i;
        }
        System.out.println("Сумма: " + sum);
        System.out.println("Числитель: " + numerator);
        System.out.println("Знаменатель: " + denominator);
    }

    public static double pow(double number, int power)
    {
        double answer = 1;
        for (int i = 0; i < power; i++)
        {
            answer *= number;
        }
        return answer;
    }
}

import java.io.PrintWriter;

import java.util.Scanner;

public class A {

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

double sum = 0;

double numerator = 1, denominator = 1;

int n = in.nextInt();

for (int i = 1; i <= n; i++)

{

denominator = pow(i,i-1);

sum += (1.0*numerator)/denominator;

numerator*=i;

}

System.out.println("Сумма: " + sum);

System.out.println("Числитель: " + numerator);

System.out.println("Знаменатель: " + denominator);

}

public static double pow(double number, int power)

{

double answer = 1;

for (int i = 0; i < power; i++)

{

answer *= number;

}

return answer;

}

Решение

Используем цикл [latex]for[/latex]: высчитываем [latex]i[/latex]-тый слагаемый, и добавляем его в сумму. В цикле высчитываем числитель, добавляем в сумму [latex]i[/latex]-тый слагаемый и домножаем числитель [latex]i[/latex]-того слагаемого на значение счётчика.
Воспользуемся веб-приложением и посчитаем сумму ряда.

Ссылки

Условие задачи (стр.251)
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)
Сходимости ряда

Related Images:

D2655Б. Сумма ряда с заданной точностью

23/10/2016 by Вадим Гордийчук

Задача

Сколько примерно надо взять членов ряда, чтобы найти его сумму с точностью до [latex]10^{-5}[/latex], если [latex]\sum\limits_{n=1}^\infty \frac{2^n}{\left(n+1\right)!}[/latex]?

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

Заданная точность.

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

Количество взятых членов ряда и их сумма.

Тесты

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

[latex]\varepsilon[/latex] [latex]k[/latex] [latex]\sum\limits_{n=1}^{k} \frac{2^n}{\left(n+1\right)!}[/latex]

1e-5 11 2.194527283416172

1 2 1.666666666666667

0.5 3 2.000000000000000

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

Программа для решения задачи D2655b
C++

#include <iostream> #include <iomanip> using namespace std; int main() { double Xn = 1, Sn = 0, epsilon; unsigned int n = 0; cin >> epsilon; while (Xn >= epsilon) { n++; Xn *= 2.0 / (n+1); Sn += Xn; } cout << fixed << setprecision(15) << n << " " << Sn << endl; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

int main()
{
    double Xn = 1, Sn = 0, epsilon; unsigned int n = 0;
    cin >> epsilon;
    while (Xn >= epsilon)
    {
        n++;
        Xn *= 2.0 / (n+1);
        Sn += Xn;
    }
    cout << fixed << setprecision(15) << n << " " << Sn << endl;
    return 0;
}

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

Для удобства введём обозначение: [latex]x_{n}=\frac{2^n}{\left(n+1\right)!}[/latex].
Чтобы доказать, что данный нам ряд [latex]\sum\limits_{n=1}^\infty \frac{2^n}{\left(n+1\right)!}[/latex] сходится, воспользуемся признаком Даламбера:
Пускай [latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}} = D[/latex]. Ряд [latex]\sum\limits_{n=1}^\infty x_n[/latex] сходится, если [latex]D < 1[/latex]. В частности, если [latex]D = 0[/latex]
Найдём [latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}}[/latex].
[latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}} = \lim\limits_{n \to \infty} \left( \frac{2^{n+1}}{\left( n+2 \right)!} \div \frac{2^{n}}{\left( n+1 \right)!} \right) = \lim\limits_{n \to \infty} \left( \frac{2 \cdot 2^{n}}{\left( n+1 \right)! \cdot \left( n+2 \right)} \cdot \frac{\left( n+1 \right)!}{2^{n}} \right) = \lim\limits_{n \to \infty} \frac{2}{n+2} = 0[/latex] Для доказательства последнего равенства [latex]\left( \lim\limits_{n \to \infty} \frac{2}{n+2} = 0 \right)[/latex] воспользуемся определением предела последовательности:
Число [latex]a[/latex] называют пределом последовательности, если для любой точности [latex]\varepsilon>0[/latex] найдётся/существует такой номер, зависящий от [latex]\varepsilon[/latex], начиная с которого все элементы последовательности попадают в интервал [latex]\left( a-\varepsilon; a+\varepsilon \right)[/latex].
В нашем случае число [latex]a[/latex] равно нулю. Поэтому доказательство будет следующим:
[latex]\forall \varepsilon>0[/latex] [latex]\exists N_{\varepsilon} \in \mathbb{N}[/latex]: [latex]\forall n\ge N_{\varepsilon}[/latex], [latex]\left| \frac{2}{n+2} \right| < \varepsilon[/latex]. Находим [latex]N_{\varepsilon}[/latex]:
[latex]\left| \frac{2}{n+2} \right| < \left| \frac{2}{n} \right| = \frac{2}{n} < \varepsilon [/latex]
[latex]\frac{2}{n} < \varepsilon[/latex]
[latex]n > \frac{2}{\varepsilon} \Rightarrow N_{\varepsilon} = \left[ \frac{2}{\varepsilon} \right] + 1 \Rightarrow \lim\limits_{n \to \infty} \frac{2}{n+2} = 0[/latex].

Итог:
Так как ряд сходится, сумма ряда стремится к некоторой константе, и можно определить точный номер [latex]k[/latex], при котором элемент (а следовательно — и сумма) ряда будет удовлетворять заданной точности. Этой точностью будет значение переменной epsilon, которое задаёт пользователь.

Ссылки

Условие задачи (страница 259);

Оригинал кода программы.

Related Images:

Входные данные	Выходные данные
[latex]\varepsilon[/latex]	[latex]k[/latex]	[latex]\sum\limits_{n=1}^{k} \frac{2^n}{\left(n+1\right)!}[/latex]
1e-5	11	2.194527283416172
1	2	1.666666666666667
0.5	3	2.000000000000000

Posted in 3. Циклы. Tagged последовательность, сумма, циклы.

D2655B. Cумма ряда с заданной точностью

15/10/2016 by Эммануил Прокопов

4

Задача
Сколько примерно надо взять членов ряда, чтобы найти его сумму с точностью до
[latex]\varepsilon [/latex], если [latex]\sum\limits _{ n=1 }^{ \infty }{ \frac { 1 }{ (2n-1)! } } [/latex]
Тесты

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

Точность Кол-во взятых членов ряда Значение суммы

1 1 2 1.1666666667

2 1е-5 5 1.1752011684

3 100 1 1

4 1e-10 7 1.1752011936

Код на C++

C++

#include <iostream> #include <iomanip> #include <cmath> using namespace std; double e = exp(1); double bin_pow(double x, int n){ if(n == 1) return x; if(n%2 == 1) return bin_pow(x, n-1)*x; double b = bin_pow(x, n/2); return b*b; } double Rn(int n){ double v = e/(2*n+1); return bin_pow(v, 2*n+1)/(1-v*v); } int main() { double eps, sum = 0, last=0; int n = 0; cin >> eps; do{ n++; if(n > 1) last /= (2*n-2)*(2*n-1); else last = 1; sum += last; } while(Rn(n) > eps); cout << fixed << setprecision(10) << "Количество взятых членов ряда: " << n << "\nЗначение суммы: " << sum; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

double e = exp(1);

double bin_pow(double x, int n){
    if(n == 1) return x;
    if(n%2 == 1) return bin_pow(x, n-1)*x;
    double b = bin_pow(x, n/2);
    return b*b;
}

double Rn(int n){
    double v = e/(2*n+1);
    return bin_pow(v, 2*n+1)/(1-v*v);
}

int main() {
    double eps, sum = 0, last=0;
    int n = 0;
    cin >> eps;
    do{
        n++;
        if(n > 1) last /= (2*n-2)*(2*n-1);
        else last = 1;
        sum += last;
    } while(Rn(n) > eps);
    cout << fixed << setprecision(10) << "Количество взятых членов ряда: " << n << "\nЗначение суммы: " << sum;
    return 0;
}

Код на Java

Java

import java.util.*; class Main { static double e = Math.exp(1); static double bin_pow(double x, int n){ if(n == 1) return x; if(n%2 == 1) return bin_pow(x, n-1)*x; double b = bin_pow(x, n/2); return b*b; } static double Rn(int n){ double v = e/(2*n+1); return bin_pow(v, 2*n+1)/(1-v*v); } public static void main (String[] args) { Scanner in = new Scanner(System.in); double eps, sum = 0, last=0; int n = 0; eps = in.nextDouble(); do{ n++; if(n > 1) last /= (2*n-2)*(2*n-1); else last = 1; sum += last; } while(Rn(n) > eps); System.out.print("Количество взятых членов ряда: " + n + "\nЗначение суммы: " + String.format("%.10f",sum)); } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.*;

class Main
{
    static double e = Math.exp(1);

    static double bin_pow(double x, int n){
        if(n == 1) return x;
        if(n%2 == 1) return bin_pow(x, n-1)*x;
        double b = bin_pow(x, n/2);
        return b*b;
    }

    static double Rn(int n){
        double v = e/(2*n+1);
        return bin_pow(v, 2*n+1)/(1-v*v);
    }

    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        double eps, sum = 0, last=0;
        int n = 0;
        eps = in.nextDouble();
        do{
            n++;
            if(n > 1) last /= (2*n-2)*(2*n-1);
            else last = 1;
            sum += last;
        } while(Rn(n) > eps);
        System.out.print("Количество взятых членов ряда: " + n + "\nЗначение суммы: " + String.format("%.10f",sum));
    }
}

Решение
Очевидно, ряд является положительным, и общий член ряда стремится к нулю. Ряд сходится по признаку Д’аламбера:
[latex] \lim\limits_{n \rightarrow \infty } \frac{ a_{n+1} }{a_{n}} = \lim\limits_{n \rightarrow \infty } \frac{ \big(2n-1\big)! }{ \big(2n+1\big)! } = \lim\limits_{n \rightarrow \infty } \frac{1}{2n \big(2n+1\big) } =0 < 1[/latex].
Оценим остаток ряда, исходя из того, что [latex]k! > \left( \frac{k}{e} \right) ^{k} , \big(k=1,2,\dots\big) [/latex]:
[latex]R_{N}<\sum\limits_{n=N+1}^\infty \left(\frac{e}{2n-1}\right)^{2n-1}\leq\sum\limits_{n=N+1}^\infty \left(\frac{e}{2N+1}\right)^{2n-1}=\left(\frac{e}{2N+1}\right)^{2N+1}\sum\limits_{i=0}^\infty \left(\frac{e}{2N+1}\right)^{2i}[/latex] Поскольку при [latex]N\geq1[/latex] [latex]\frac{e}{2N+1}<1[/latex]:
[latex]R_{N} < \left(\frac{e}{2N+1}\right)^{2N+1}\frac{1}{1-\left(\frac{e}{2N+1}\right)^2}[/latex]
В переменной sum хранится текущее значение суммы ряда, в last — последний рассмотренный член ряда. В начале работы программы вводится требуемая точность eps. Можно заметить, что для получения [latex]n[/latex]-го члена ряда достаточно разделить предыдущий на [latex]\left(2n-2\right)\cdot\left(2n-1\right)[/latex], однако необходимо отдельно рассмотреть случай, когда [latex]n = 1[/latex]. В цикле увеличиваем [latex]n[/latex], находим значение следующего члена ряда и прибавляем к sum, пока остаток ряда не станет достаточно маленьким. Оцениваем остаток ряда при помощи функции Rn(int n). Во время её работы может потребоваться возведение числа в большую степень, делаем это по алгоритму бинарного возведения в степень.

Ссылка на код на ideone.com: здесь (C++) и здесь (Java).
Условие задачи (стр. 259)

Related Images:

Posted in 3. Циклы. Tagged последовательность, сумма, факториал, циклы.

Совершенные числа

17/08/2016 by Макогон Владимир Сакович

0

Задача. Найдите все чётные совершенные числа не превышающие заданного числа[latex]M[/latex].

Напомним, что натуральное число [latex]n[/latex] называют совершенным, если оно равно сумме всех своих делителей, не считая его самого. Известно, что все совершенные числа — четные и что первое совершенное число из натурального ряда равно 6. Этим объясняется правило изменения параметра внешнего цикла. Так как все натуральные числа имеют своим делителем единицу, полагаем начальное значение суммы делителей числа S = 1. Во внутреннем цикле организуется перебор всех делителей текущего значения N. Из теории чисел известно, что такому испытанию имеет смысл подвергать числа от 2 до [latex]\frac{n}{2}[/latex], либо даже до [latex]\sqrt{n}[/latex]. Этот не очень совершенный алгоритм реализован в следующем коде:

Совершенные числа 1
C++

#include <iostream> #include <cmath> using namespace std; int main() { unsigned long long M; cin >> M; for (unsigned long long n = 4; n <= M; n += 2) { unsigned long long S = 1; for (unsigned long long j = 2; j <= sqrt(n) && S <= n; j++) { if (n % j == 0) S += n / j + j; } if (n == S) cout << n << " "; } return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

int main() {
    unsigned long long M;
    cin >> M;
    for (unsigned long long n = 4; n <= M; n += 2) {
        unsigned long long S = 1;
        for (unsigned long long j = 2; j <= sqrt(n) && S <= n; j++) {
            if (n % j == 0) S += n / j + j;
        }
        if (n == S) cout << n << " ";
    }
    return 0;
}

Обратите внимание, что во внутреннем цикле мы прекращаем искать делители, если их сумма уже превышает исходное число.

Теперь рассмотрим другой подход, позволяющий ускорить вычисления. Используем алгоритм нахождения совершенных чисел, более эффективный по сравнению с приведенным ранее. Этот алгоритм основан на известном из теории чисел утверждении Ферма о том, что если натуральное число [latex]p = 2^{k+1}-1[/latex] простое, то число [latex]n = 2^k \cdot (2^{k+1}-1)=p \cdot 2^k[/latex] — совершенное ([latex]k = 1,2,\ldots[/latex]).
Функция prime() определяет, является ли число [latex]p[/latex] простым. Обратите внимание, что функция проверяет в качестве возможных делителей исходного числа только нечетные числа, так как само испытуемое число — нечетное.

Совершенные числа 2
C++

// Найти все чётные совершенные числа из unsigned long long #include <iostream> #include <cmath> using namespace std; // Подпрограмма определяет, является ли число n простым bool is_prime(unsigned long long n) { unsigned long long i = 3; while (i < sqrt(n)) { if (n % i == 0) return false; i += 2; } return true; } int main() { unsigned long long p = 1, n = 1; while (p * n < (4 * n - 1) * 2 * n) { // пока числа увеличиваются p = 2 * n - 1; if (is_prime(p)) cout << n * p << " "; n <<= 1; } return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Найти все чётные совершенные числа из unsigned long long
#include <iostream>
#include <cmath>
using namespace std;

// Подпрограмма определяет, является ли число n простым
bool is_prime(unsigned long long n) {
    unsigned long long  i = 3;
    while (i < sqrt(n)) {
        if (n % i == 0) return false;
        i += 2;
    }
    return true;
}

int main() {
    unsigned long long p = 1, n = 1;
    while (p * n < (4 * n - 1) * 2 * n) { // пока числа увеличиваются
        p = 2 * n - 1;
        if (is_prime(p)) cout << n * p << " ";
        n <<= 1;
    }
    return 0;
}

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

Related Images:

Posted in 3. Циклы, Творческие задачи. Tagged простые числа, совершенные числа, тест на простоту, Ферма.

Лабиринт

02/07/2016 by Маша Лукьянова

6

Условие:

           Имя входного файла:            стандартный поток ввода

       Имя выходного файла:             стандартный поток вывода

           Ограничение по времени:      2 second

         Ограничение по памяти:      64 мегабайт

Задан лабиринт [latex] N \times N [/latex], некоторые клетки которого могут быть заняты. Дан путь робота длины [latex] k [/latex] по этому лабиринту без указания его начального положения. Известно, что робот до начала движения стоит в одной из свободных клеток. Необходимо определить наименьшее количество передвижений по пути, после которого можно точно определить, где находится робот.

Задача взята из 1-го раунда KPI OPEN 2013 года.

Формат входного файла:

Первая строка входного файла содержит два целых числа через пробел $$ N (1 \leq N \leq 100) $$ и $$k (0 \leq k \leq 10^{5}) $$. В следующих [latex] N [/latex] строках задана карта лабиринта как совокупность 0 и 1 без пробелов: 1 – занятая клетка, 0 – свободная. В последней строке дана последовательность из $$ k (0 \leq k \leq 10^{5} ) $$ символов. Символы задают движение робота по лабиринту: символ [latex] U [/latex] — вверх, [latex] D [/latex] — вниз, [latex] R [/latex] —вправо, [latex] L [/latex] — влево. Других символов в строке передвижений нет, все символы в верхнем регистре латиницы.

Формат выходного файла:

В единственной строке выходного файла выведите единственное целое число не меньше нуля — наименьшее количество передвижений по пути, после которого можно точно определить местоположение робота. Если ответ не существует, либо входные данные некорректны, выведите -1.

Тесты:

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

1
2 0

11

01
0

2
2 0

11

11
-1

3
2 1

11

01

R
-1

4
3 3

000

010

000

RDU
2

5 5 5
00010
10001
00100
10100
01101
RDUUU 4

Решение:

Если попробовать решить эту задачу «в лоб», то решение не будет удовлетворять пределу по времени, так как в худшем случае, нам надо перебрать $$ 10^{4} $$ возможных начальных позиций и совершить из них $$ 10^{5} $$ ходов, что в результате дает $$ 10^{9} $$ операций.

Решение «в лоб»:

Заведем список позиций в лабиринте, которым соответствуют элементы матрицы, в которые может попасть робот. В изначальном состоянии, без просмотра пути передвижения робота, это будут все позиции в лабиринте, где значение равно $$ 0 $$. После чего, проходя путь робота по шагам, будем для всех позиций в списке проверять:

Если мы вышли за границу матрицы, или в клетке, в которую мы собираемся перейти стоит $$ 1 $$, тогда удаляем эту позицию, поскольку она для нас недостижима.

Иначе ничего не делаем.

Если количество текущих вариантов пути стало равным $$ 1 $$, то мы запоминаем количество ходов при которой была достигнута данная ситуация.

Так будем делать до тех пор, пока робот закончил свой путь.

Если после всех проделанных нами операций остался один вариант полностью пройденного пути, тогда ответ найден. А именно это будет ход, после которого у нас кол-во удовлетворяющих позиций стало равным $$ 1 $$. В любом другом случае ответ нельзя определить однозначно.

Другая идея состоит в том, чтобы построить карту «переходов», в которой будет храниться номер хода, на котором робот впервые попал в эту клетку и ее координаты. Эта карта играет роль некоторого шаблона полного пути робота и «накладывая» его на каждый элемент матрицы в качестве начальной позиции, мы проверяем мог ли данный элемент матрицы служить «пунктом отправления» робота. Если такой элемент есть и он единственен, значит, можно однозначно определить начальное положение робота, но для того чтобы определить минимальное количество требуемых ходов-нужно последовательно удалять последние ходы из карты, «накладывая» изменившийся шаблон на каждый элемент, до тех пор, пока количество элементов удовлетворяющих шаблону не возрастет. Что значит, что мы получим номер решающего хода после которого судьба робота решится однозначно, значит ответом будет предыдущий ход. Стоит отметить, что если в карте останется всего лишь один элемент (соответствующий первому ходу), то расположение робота определялось однозначно первым ходом.

C++

#include <iostream> #include <vector> #include <string> #include <algorithm> #include <stack> #include <set> #include <list> #include <map> #define ll long long int #define X first #define Y second #include <iostream> using namespace std; int main() { int n, k; cin >> n >> k; char maze[n][n];//лабиринт for(int i = 0; i < n; ++i){ getchar(); for(int j = 0; j < n; ++j){ maze[i][j] = getchar(); } } getchar(); char path[k+1]; //путь for(int i = 0; i < k; ++i){ path[i + 1] = getchar(); } set<pair<int, int> > visited; //ячейки, в которых мы побывали map<int, pair<int, int> > nodes; // узлы, которые должен пройти робот (номер хода, координаты) pair<int, int> cur = {0, 0}; visited.insert(cur); nodes[0] = cur; //проходим весь путь for(int i = 1; i <= k; ++i){ if(path[i] == 'L'){ --cur.X; if(!visited.count(cur)){ nodes[i] = cur; visited.insert(cur); } }else if(path[i] == 'R'){ ++cur.X; if(!visited.count(cur)){ nodes[i] = cur; visited.insert(cur); } }else if(path[i] == 'U'){ --cur.Y; if(!visited.count(cur)){ nodes[i] = cur; visited.insert(cur); } }else if(path[i] == 'D'){ ++cur.Y; if(!visited.count(cur)){ nodes[i] = cur; visited.insert(cur); } } } int count = 0; map<int, int> ans; bool ok = false; for(; nodes.size();){ for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ for(pair<int, pair<int, int> > a : nodes){ if(j + a.Y.X < 0 || j + a.Y.X >= n || // не вышли ли за пределы по строкам i + a.Y.Y < 0 || i + a.Y.Y >= n || // не вышли ли за пределы по столбцам maze[i + a.Y.Y][j + a.Y.X] == '1'){ //не попали ли на 1-цу --count; break; } } ++count; } } auto t = --nodes.end(); ans[count] = t->X; nodes.erase(t); count = 0; if(ans.size() == 2) break; if(!ok){ ok = 1; if(ans.begin()->X != 1){ cout << -1 << endl; return 0; } } } if(ans.size() == 1 && ans.begin()->X == 1){ cout << ans.begin()->Y << endl; }else if(ans.size() == 2 && ans.begin()->X == 1){ cout << ans.begin()->Y << endl; }else{ cout << -1 << endl; } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <set>
#include <list>
#include <map>

#define ll long long int
#define X first
#define Y second
#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    char maze[n][n];//лабиринт
    for(int i = 0; i < n; ++i){
        getchar();
        for(int j = 0; j < n; ++j){
            maze[i][j] = getchar();
        }
    }
    getchar();
    char path[k+1]; //путь
    for(int i = 0; i < k; ++i){
        path[i + 1] = getchar();
    }
    set<pair<int, int> > visited;
        //ячейки, в которых мы побывали
    map<int, pair<int, int> > nodes;
        // узлы, которые должен пройти робот (номер хода, координаты)
    pair<int, int> cur = {0, 0};
    visited.insert(cur);
    nodes[0] = cur;
    //проходим весь путь
    for(int i = 1; i <= k; ++i){
        if(path[i] == 'L'){
            --cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'R'){
            ++cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'U'){
            --cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'D'){
            ++cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }
    }
    int count = 0;
    map<int, int> ans; bool ok = false;
    for(; nodes.size();){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                for(pair<int, pair<int, int> > a : nodes){
                    if(j + a.Y.X < 0 || j + a.Y.X >= n ||
                              // не вышли ли за пределы по строкам
                        i + a.Y.Y < 0 || i + a.Y.Y >= n ||
                              // не вышли ли за пределы по столбцам
                        maze[i + a.Y.Y][j + a.Y.X] == '1'){
                              //не попали ли на 1-цу
                        --count;
                        break;
                    }
                }
                ++count;
            }
        }
        auto t = --nodes.end();
        ans[count] = t->X;
        nodes.erase(t);
        count = 0;
        if(ans.size() == 2) break;
        if(!ok){
            ok = 1;
            if(ans.begin()->X != 1){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    if(ans.size() == 1 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else if(ans.size() == 2 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else{
        cout << -1 << endl;
    }
}

Submission.

Related Images:

Posted in 2. Программы с ветвлением, 3. Циклы, 6. Многомерные массивы, 8. Строки string, Творческие задачи. Tagged KPI open 2013, map, pair, set, КПИ, лабиринт, найти местоположение робота.

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

26/06/2016 by Кирилл Демиденко

1

Задача

Даны значения чисел [latex]n[/latex] и [latex]a[/latex]. Вычислить [latex]\sum_{i=1}^{n}
i* a^{i}[/latex].

Тесты

Ввод: 3 2 6 4 10 2

Вывод: 34 30948 18434

C++

#include <iostream> #include <cmath> using namespace std; int main() { int n, a; long long sum = 0; cin >> n >> a; for (int i = 1; i <= n; i++){ //пока i не будет равно n sum += pow(a,i)*i ; //программа будет суммировать эту формулу } //с увеличением значения переменной i на 1 if (n=1){ cout<<a; } cout << sum; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

int main() {
    int n, a;
    long long sum = 0;
    cin >> n >> a;
    for (int i = 1; i <= n; i++){ //пока i не будет равно n
        sum += pow(a,i)*i ;   //программа будет суммировать эту формулу
    }                             //с увеличением значения переменной i на 1
        if (n=1){
         cout<<a;
}
    cout << sum;
    return 0;
}

Вводим два числа [latex]n[/latex],[latex]a[/latex] и [latex]sum[/latex] . Задаем цикл и суммируем до тех пор, пока [latex]i[/latex] не будет равно значению [latex]n[/latex].

Related Images:

Posted in 3. Циклы. Tagged сумма.

Post navigation

← Older posts

Newer posts →

Search

1. Линейные вычисления

2. Программы с ветвлением

3. Циклы

4. Потоковая обработка

5. Массивы

6. Многомерные массивы

7. Строки c-string

8. Строки string

9. Последовательные контейнеры

A. Сортировки и жадность

B. Стеки-деки-очереди

C. Ассоциативные контейнеры

D. Графы

E. Дерево отрезков

F. Динамическое программирование

Игры программистов

Спортивное программирование

Творческие задачи

Численный анализ

⌂ Организационные

Студенты 2020

Введите адрес для отправки новостей

E-mail

Іванов Вячеслав Володимирович (22)
Ілларіонова Марія Валеріївна (20)
Зелінський Вячеслав Олександрович (19)
Вустянюк Ігор Дмитрович (19)
Сплошнов Кирилл (18)
Таран Таня (17)
Гордийчук Вадим (15)
Корнилова Таня (14)
Денисова Ольга (14)
Калачьов Андрій Сергійович (14)
Студенты 2019

Студенты 2018

Студенты 2017

Студенты 2016

Студенты 2015

Студенты 2014

Proudly powered by WordPress | Theme: Sunspot by WordPress.com.

№	Входные данные	Выходные данные
	Точность	Кол-во взятых членов ряда	Значение суммы
1	1	2	1.1666666667
2	1е-5	5	1.1752011684
3	100	1	1
4	1e-10	7	1.1752011936

№	Входные данные	Выходные данные
1	2 0 11 01	0
2	2 0 11 11	-1
3	2 1 11 01 R	-1
4	3 3 000 010 000 RDU	2
5	5 5 00010 10001 00100 10100 01101 RDUUU	4