Ю3.25

27/01/2016 by Сабиров Ильдар

Задача.

Для заданных [latex]m[/latex] и [latex]n[/latex] вычислить число сочетаний [latex]C_m^n[/latex] непосредственно: [latex]C_m^n=\frac{m!}{n!(m-n)!}[/latex] и по рекуррентным формулам:

• [latex]C_m^n=\frac{m-n+1}{n}\cdot C_m^{n-1}, C_m^1=m;[/latex]

• [latex]C_m^n=C_{m-1}^{n-1}+C_{m-1}^n;C_m^1=m,C_m^m=1.[/latex]

Сравнить время вычислений(или число операций) по каждой формуле.

Тесты:

[latex]m[/latex]	[latex]n[/latex]	[latex]C_m^n[/latex]	Комментарий
122	12	По первой формуле равно: 1.29803e+16 По второй формуле равно: 1.29803e+16 По третьей формуле равно: 12980291311103116 Первая формула сработала за(в милисек):0.056 Вторая формула сработала за(в милисек):0.009 Третья формула сработала за(в милисек):0.021	Пройдено
14	5	По первой формуле равно: 2002 По второй формуле равно: 2002 По третьей формуле равно: 2002 Первая формула сработала за(в милисек):0.064 Вторая формула сработала за(в милисек): 0.009 Третья формула сработала за(в милисек): 0.012	Пройдено
16	7	По первой формуле равно: 11440 По второй формуле равно: 11440 По третьей формуле равно: 11440 Первая формула сработала за(в милисек):0.067 Вторая формула сработала за(в милисек): 0.009 Третья формула сработала за(в милисек): 0.012	Пройдено

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

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

int main() {
	unsigned int start_time1,start_time2,start_time3,search_time1,search_time2,search_time3;
	int i,y,u,m,n,h,j,x;
	long long c3=0;
	cin>>m;
	cin>>n;
	double k=m,c2=1,c1;
	long long D[m+3][n+1];
	double b=m-n, q=n, w=m, z=b;
	if(m>n && n>=1)
	{
		start_time1 = clock();
		for(i=1;i<n;i++) {q=q*i;}
		for(y=1;y<m;y++) {w=w*y;}
		for(u=1;u<b;u++) {z=z*u;}
		c1=w/(q*z);
		cout<<"По первой формуле равно:"<<c1<<" "<<endl;
		search_time1 = clock() - start_time1;
		
		start_time2 = clock();
		for(i=n;i>=1;i--)
		{
			c2*=(k-i+1)/i;
		}
		cout<<"По второй формуле равно:"<<c2<<" "<<endl;
		search_time2 = clock() - start_time2;
		
		start_time3 =  clock();
		for(y=1;y<=m;y++) // Для каждой строки.
		{
			D[y][1]=y;
			D[y][y]=1;
			for(x=2;x<=n && x<y;x++)
			{
				D[y][x]=D[y-1][x-1]+D[y-1][x];
			}
		}
		c3=D[m][n];
		cout<<"По третьей формyле равно:"<<c3<<" "<<endl;
		search_time3 = clock() - start_time3;
	}
	else if(m<n) {
		cout<<"invalid";
	}
	
	cout<<"Первая формула сработала за:(в милисек)"<<((double)search_time1/CLOCKS_PER_SEC)*1000<<endl;
	cout<<"Вторая формула сработала за:(в милисек)"<<(double)search_time2/CLOCKS_PER_SEC*1000<<endl;
	cout<<"Третья формула сработала за:(в милисек)"<<(double)search_time3/CLOCKS_PER_SEC*1000<<endl;
	if(search_time1<search_time2 && search_time1<search_time3) { cout<<"Первая формула выполняется быстрее."<<endl; }
	else if(search_time2<search_time1 && search_time2<search_time3) { cout<<"Вторая формула выполняется быстрее."<<endl; }
	else if(search_time3<search_time2 && search_time3<search_time1) { cout<<"Третья формула выполняется быстрее."<<endl; }
	return 0;
}

#include <iostream>

#include <ctime>

using namespace std;

int main() {

unsigned int start_time1,start_time2,start_time3,search_time1,search_time2,search_time3;

int i,y,u,m,n,h,j,x;

long long c3=0;

cin>>m;

cin>>n;

double k=m,c2=1,c1;

long long D[m+3][n+1];

double b=m-n, q=n, w=m, z=b;

if(m>n && n>=1)

{

start_time1 = clock();

for(i=1;i<n;i++) {q=q*i;}

for(y=1;y<m;y++) {w=w*y;}

for(u=1;u<b;u++) {z=z*u;}

c1=w/(q*z);

cout<<"По первой формуле равно:"<<c1<<" "<<endl;

search_time1 = clock() - start_time1;

start_time2 = clock();

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

{

c2*=(k-i+1)/i;

}

cout<<"По второй формуле равно:"<<c2<<" "<<endl;

search_time2 = clock() - start_time2;

start_time3 = clock();

for(y=1;y<=m;y++) // Для каждой строки.

{

D[y][1]=y;

D[y][y]=1;

for(x=2;x<=n && x<y;x++)

{

D[y][x]=D[y-1][x-1]+D[y-1][x];

}

c3=D[m][n];

cout<<"По третьей формyле равно:"<<c3<<" "<<endl;

search_time3 = clock() - start_time3;

}

else if(m<n) {

cout<<"invalid";

}

cout<<"Первая формула сработала за:(в милисек)"<<((double)search_time1/CLOCKS_PER_SEC)*1000<<endl;

cout<<"Вторая формула сработала за:(в милисек)"<<(double)search_time2/CLOCKS_PER_SEC*1000<<endl;

cout<<"Третья формула сработала за:(в милисек)"<<(double)search_time3/CLOCKS_PER_SEC*1000<<endl;

if(search_time1<search_time2 && search_time1<search_time3) { cout<<"Первая формула выполняется быстрее."<<endl; }

else if(search_time2<search_time1 && search_time2<search_time3) { cout<<"Вторая формула выполняется быстрее."<<endl; }

else if(search_time3<search_time2 && search_time3<search_time1) { cout<<"Третья формула выполняется быстрее."<<endl; }

return 0;

}

Ход решения:

1.С помощью цикла [latex]for[/latex] и функции [latex]clock[/latex] я нахожу число сочетаний и время вычислений.

Чтобы посчитать время вычислений по второй рекуррентной формуле я воспользовался Треугольником Паскаля.

Треугольник Паскаля хранится в двумерном массиве и заполняется по указанной в условии формуле начиная с верхнего левого угла.

2.Вывожу число сочетаний

3.С помощью условного оператора [latex]if[/latex] я сравниваю время вычислений.

Ссылка на код

Related Images:

Mloop 21

21/12/2015 by Максим Носов

Задача

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

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

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

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

Сумма ряда.

Тесты

№	Точность [latex]\varepsilon [/latex]	Сумма ряда	Количество членов
1	1	3	2
2	0.5	8.502	8
3	0.1	9.156	12
4	0.01	9.307	18

Код

#include <iostream>
using namespace std;

int main() {
	double fib1=1,fib2=1,fib3,sum=3,E,a=1; //задаем переменные
	int k=2;
	cin>>E; //вводим точность, с которой будут происходить вычисления //если точность равна 1 то сумма последовательности 
	if(E==2 || E==1)cout<<2<<endl<<3; //если точность равна 1 или 2 по сумма будет равнна сумме двух первых членов последовательности
	else if(E<1){
		for(int i=3;a>=E;i++){ //задаем цикл:пока следующее слагаемое больше точности
			fib3=fib1+fib2;
			a=i/fib3; //слагаемое
			sum+=a;
			fib1=fib2;
			fib2=fib3;
			//k++;  //считаем количество слагаемых, для того чтобы потом проверить результат
		}
	//cout<<k<<endl;
        cout<<sum;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double fib1=1,fib2=1,fib3,sum=3,E,a=1; //задаем переменные

int k=2;

cin>>E; //вводим точность, с которой будут происходить вычисления //если точность равна 1 то сумма последовательности

if(E==2 || E==1)cout<<2<<endl<<3; //если точность равна 1 или 2 по сумма будет равнна сумме двух первых членов последовательности

else if(E<1){

for(int i=3;a>=E;i++){ //задаем цикл:пока следующее слагаемое больше точности

fib3=fib1+fib2;

a=i/fib3; //слагаемое

sum+=a;

fib1=fib2;

fib2=fib3;

//k++; //считаем количество слагаемых, для того чтобы потом проверить результат

}

//cout<<k<<endl;

cout<<sum;

}

return 0;

}

Решение

Предлагаю следующее решение. Вычисляем первые два члена суммы:[latex]\sum _{i=1}^{2}{\frac{i}{fib(i)}}=1+\frac{1}{2}[/latex]. Каждое следующее слагаемое находим по формуле [latex]\frac{i}{fib(i)}[/latex] и записываем в переменную [latex]a[/latex], которую прибавляем к переменной [latex]sum[/latex], где хранится сумма, известная нам на данный момент (изначально это сумма первых двух членов) . [latex]fib_1[/latex] и [latex]fib_2[/latex] это два последних числа Фибоначчи, которые нам нужны для вычисления следующего [latex]fib_3[/latex]. Продолжаем искать слагаемые пока следующее слагаемое больше точности [latex]\varepsilon [/latex]. Вводим дополнительную переменную [latex]k[/latex] для того чтоб сосчитать количество слагаемых. Затем можно проверить правильность вычислений тут, подставляя [latex]k[/latex] как количество слагаемых.

Ссылка на код.

Related Images:

MLoops 11

19/12/2015 by Катя Писова

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел $n > 0$ (количество столбцов) и $m > 0$ (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр $k < n$ .
Замечание 2. Многоточие означает продолжение последовательности. Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

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

Три числа: количество столбцов и строк, параметр [latex]k[/latex].

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

+-------+-------+-------+
|123...k|123...k|123...k|
|23...k1|23...k1|23...k1|
|3...k12|3...k12|3...k12|
|.......|.......|.......|
|k123...|k123...|k123...|
+-------+-------+-------+
|123...k|123...k|123...k|
|23...k1|23...k1|23...k1|

+-------+-------+-------+

|123...k|123...k|123...k|

|23...k1|23...k1|23...k1|

|3...k12|3...k12|3...k12|

|.......|.......|.......|

|k123...|k123...|k123...|

+-------+-------+-------+

|123...k|123...k|123...k|

|23...k1|23...k1|23...k1|

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

#include <iostream>
using namespace std;
 
int main() 
{
	int m, n, k;
	cin >> m >> n >> k;
	for (int i = 0; i < m; i++)
	{
		if (i % (k + 1) == 0)
		{
			for (int j = 0; j < n; j++)
			{
				cout << (j % (k + 1) == 0 ? "+" : "-");
			}
		}
		else
		{
			for (int j = 0; j < n; j++)
			{
				if (j % (k + 1) == 0)
				{
					cout << "|";
				}
				else
				{
					int a = (j % (k + 1) + i % (k + 1) - 1) % k;
					cout << (a == 0 ? k : a);
				}
			}
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int m, n, k;

cin >> m >> n >> k;

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

{

if (i % (k + 1) == 0)

{

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

{

cout << (j % (k + 1) == 0 ? "+" : "-");

}

else

{

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

{

if (j % (k + 1) == 0)

{

cout << "|";

}

else

{

int a = (j % (k + 1) + i % (k + 1) - 1) % k;

cout << (a == 0 ? k : a);

}

cout << endl;

}

return 0;

}

Решение:

Для построения данной таблицы нужно найти закономерность чередования символов в таблице. Решение данной задачи можно осуществить с помощью двух циклов. Первый отвечает за строки, а второй — за столбцы. Пусть нумерация строк и столбцов начинается с нуля. Тогда, если номер строчки нацело делится на [latex](k+1)[/latex], то рассматриваем столбцы этой строчки. Если номер столбца нацело делится на [latex](k+1)[/latex], то записываем «+», иначе «-«. Если номер строки не делится нацело на [latex](k+1)[/latex], а номер столбца в этой строке — делится, то записываем «|». Если номер строки и столбца не делятся нацело на [latex](k+1)[/latex], то создаем переменную, с помощью которой будем заполнять таблицу цифрами. Так как, каждый столбик и каждая строка имеют свой номер, то с помощью нахождения суммы остатка от деления строки и столбца на [latex](k+1)[/latex] будем находит значение элемента, стоящего на пересечении [latex]i- [/latex]ой строки и [latex]i-[/latex]ого столбца, но этого не достаточно, в таблице есть перестановка, чтобы ее реализовать отнимаем от суммы единицу, делая этим сдвиг вправо. Также от полученного результата нужно найти остаток от деления на параметр [latex]k[/latex] для того, чтобы выполнялась правильная последовательность символов. Если результат вычисления переменной равен нулю, то записываем значение параметра [latex]k[/latex], иначе — результат вычисления переменной.

Тесты:

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

+----
|1234
|2345
|3456
|4567

+----

|1234

|2345

|3456

|4567

+-----+-----+
|12345|12345|
|23451|23451|
|34512|34512|
|45123|45123|
|51234|51234|
+-----+-----+
|12345|12345|
|23451|23451|
|34512|34512|
|45123|45123|
|51234|51234|
+-----+-----+
|12345|12345|

+-----+-----+

|12345|12345|

|23451|23451|

|34512|34512|

|45123|45123|

|51234|51234|

+-----+-----+

|12345|12345|

|23451|23451|

|34512|34512|

|45123|45123|

|51234|51234|

+-----+-----+

|12345|12345|

+-----+
|12345|
|23451|
|34512|
|45123|
|51234|
+-----+
|12345|
|23451|

+-----+

|12345|

|23451|

|34512|

|45123|

|51234|

+-----+

|12345|

|23451|

+-------+-------+-------+-----
|1234567|1234567|1234567|12345
|2345671|2345671|2345671|23456
|3456712|3456712|3456712|34567
|4567123|4567123|4567123|45671
|5671234|5671234|5671234|56712
|6712345|6712345|6712345|67123
|7123456|7123456|7123456|71234
+-------+-------+-------+-----
|1234567|1234567|1234567|12345
|2345671|2345671|2345671|23456
|3456712|3456712|3456712|34567
|4567123|4567123|4567123|45671
|5671234|5671234|5671234|56712
|6712345|6712345|6712345|67123
|7123456|7123456|7123456|71234
+-------+-------+-------+-----

+-------+-------+-------+-----

|1234567|1234567|1234567|12345

|2345671|2345671|2345671|23456

|3456712|3456712|3456712|34567

|4567123|4567123|4567123|45671

|5671234|5671234|5671234|56712

|6712345|6712345|6712345|67123

|7123456|7123456|7123456|71234

+-------+-------+-------+-----

|1234567|1234567|1234567|12345

|2345671|2345671|2345671|23456

|3456712|3456712|3456712|34567

|4567123|4567123|4567123|45671

|5671234|5671234|5671234|56712

|6712345|6712345|6712345|67123

|7123456|7123456|7123456|71234

+-------+-------+-------+-----

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

Related Images:

А406

18/12/2015 by Сабиров Ильдар

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n	Матрица [latex]x_{ij}, i=1,2.[/latex]	Длина наибольшего отрезка	Комментарий
3	2 8 4 9 1 5	10	Пройдено
4	6 14 2 1 9 3 8 0	13.3417	Пройдено
5	1 8 4 3 7 2 9 5 0 11	11.7047	Пройдено

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

#include <iostream>
#include <cmath>
using namespace std;
int main() 
{
	double max = 0;
	int K=2,L,x=0,y=1;
	cin >> L;
	int D[K][L];
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < L; j++)
		{
			cin>>D[i][j];
		}
	}
	for (int i = 0; i < L-1; i++)
	{
		for (int j = 0; j < L; j++)
		{
			double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));
			if(q>max)
			{
				max=q;
			}
		}
	}
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < L; j++)
		{
			cout<<D[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<max;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double max = 0;

int K=2,L,x=0,y=1;

cin >> L;

int D[K][L];

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

{

for (int j = 0; j < L; j++)

{

cin>>D[i][j];

}

for (int i = 0; i < L-1; i++)

{

for (int j = 0; j < L; j++)

{

double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));

if(q>max)

{

max=q;

}

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

{

for (int j = 0; j < L; j++)

{

cout<<D[i][j]<<" ";

}

cout<<"\n";

}

cout<<max;

return 0;

}

Ход решения:

Вводим матрицу построчно (не очень удобно).
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
[latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.
Ссылка на код

Related Images:

Mloops 21

11/11/2015 by Женя Максимова

Задача.Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n>0[/latex] (количество столбцов) и [latex]m>0[/latex] (количество строк).
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

1+12+33+64+105+156+217+288
12+33+64+105+156+217+288+1
33+64+105+156+217+288+1+12
64+105+156+217+288+1+12+33
105+156+217+288+1+12+33+64
156+217+288+1+12+33+64+105
217+288+1+12+33+64+105+156

Тесты

№	[latex]m[/latex]	[latex]n[/latex]	Результат
1	5	13	1+12+33+64+10 12+33+64+105+ 33+64+105+1+1 64+105+1+12+3 105+1+12+33+6
2	8	11	1+12+33+64+ 12+33+64+1+ 33+64+1+12+ 64+1+12+33+ 1+12+33+64+ 12+33+64+1+ 33+64+1+12+ 64+1+12+33+
3	11	20	1+12+33+64+105+156+2 12+33+64+105+156+217 33+64+105+156+217+1+ 64+105+156+217+1+12+ 105+156+217+1+12+33+ 156+217+1+12+33+64+1 217+1+12+33+64+105+1 1+12+33+64+105+156+2 12+33+64+105+156+217 33+64+105+156+217+1+ 64+105+156+217+1+12+

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

#include <iostream>
#include <stdio.h>
#include<cmath>
using namespace std;
int m, n, max_q; // длина и ширина таблицы, максимальное количество чисел в строке

int element(int i) // формула для i-того элемента последовательности
{
 i++;
 return i*i+4*(i*i-i); 
}
int length_of_element(int el) // длина i-того элемента
{
 if( el==0|| el==1 ) 
   return 1;
 return ceil(log10(el));
}

int max_quantity() // максимальное количество чисел в строке
{
 int max_q=0;
 int length=0;
 for(int j=0; true; j++) 
  {
	 int elem = element(j);
	 int  length_el = length_of_element(elem);
	 if(length + length_el <= n) // проверяем, "поместится" ли в строку очередное число 
    {
      length += length_el;
      max_q++;
      if(length == n)
        return max_q;
    }
	 else // если число не "влезает", добавляем "+"
	{
	  max_q++;
	  return max_q;
	}
   if(length+1 <= n) // если число "поместилось", но осталось место еще для одного символа, тоже добавляем "+"
    {
     length += 1;
     if(length == n)
      return max_q;
    }
  }
 return max_q; // такая ситуация невозможна
}

int line(int i) // печать i-той строки
{
 int length=0;
 for(int jj=i; true; jj++)
    {
     int j = jj % max_q; // формула циклического сдвига чисел в строке
     int  elem = element(j); // число которое мы будем выводить
     int  length_el = length_of_element(elem); // длина числа
     if(length + length_el <= n) // если полученная нами длина все еще меньше заданного количества столбцов, мы выводим число 
        {
         length += length_el;
         cout << elem;
         if(length == n)
            {
             cout << endl;
             return length;
            }
        }
     else // если длина получается больше, мы "отрезаем" от числа нужное количество символов
        {
         int excess = length+length_el-n;
         for(int z = 0; z < excess; ++z) elem /= 10;
         cout << elem << endl;
         return length;
        }

     if(length + 1 <= n) // проверяем, нужно ли выводить "+"
      {
        length += 1; cout << "+";
        if(length == n)
        {
          cout << endl;
          return length;
        }
      }
    }
return 0;
}

int main()
{
 cin >> m >> n; // параметры таблицы
 max_q = max_quantity(); // вычисляем максимально возможное количество чисел в строке
 for(int i=0; i<m; i++) line(i); // вывод таблицы
 return 0;
}

#include <iostream>

#include <stdio.h>

#include<cmath>

using namespace std;

int m, n, max_q; // длина и ширина таблицы, максимальное количество чисел в строке

int element(int i) // формула для i-того элемента последовательности

{

i++;

return i*i+4*(i*i-i);

}

int length_of_element(int el) // длина i-того элемента

{

if( el==0|| el==1 )

return 1;

return ceil(log10(el));

}

int max_quantity() // максимальное количество чисел в строке

{

int max_q=0;

int length=0;

for(int j=0; true; j++)

{

int elem = element(j);

int length_el = length_of_element(elem);

if(length + length_el <= n) // проверяем, "поместится" ли в строку очередное число

{

length += length_el;

max_q++;

if(length == n)

return max_q;

}

else // если число не "влезает", добавляем "+"

{

max_q++;

return max_q;

}

if(length+1 <= n) // если число "поместилось", но осталось место еще для одного символа, тоже добавляем "+"

{

length += 1;

if(length == n)

return max_q;

}

return max_q; // такая ситуация невозможна

}

int line(int i) // печать i-той строки

{

int length=0;

for(int jj=i; true; jj++)

{

int j = jj % max_q; // формула циклического сдвига чисел в строке

int elem = element(j); // число которое мы будем выводить

int length_el = length_of_element(elem); // длина числа

if(length + length_el <= n) // если полученная нами длина все еще меньше заданного количества столбцов, мы выводим число

{

length += length_el;

cout << elem;

if(length == n)

{

cout << endl;

return length;

}

else // если длина получается больше, мы "отрезаем" от числа нужное количество символов

{

int excess = length+length_el-n;

for(int z = 0; z < excess; ++z) elem /= 10;

cout << elem << endl;

return length;

}

if(length + 1 <= n) // проверяем, нужно ли выводить "+"

{

length += 1; cout << "+";

if(length == n)

{

cout << endl;

return length;

}

return 0;

}

int main()

{

cin >> m >> n; // параметры таблицы

max_q = max_quantity(); // вычисляем максимально возможное количество чисел в строке

for(int i=0; i<m; i++) line(i); // вывод таблицы

return 0;

}

Алгоритм

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

[latex]n^2+4\cdot(n^2-n)[/latex]

Для удобства выполнения циклических операций я изменила формулу последовательности так, чтобы результат был верным при нумерации с нуля.

В каждой следующей строке мы сдвигаем последовательность на одно число влево.

Чтобы число столбцов [latex]n[/latex] соответствовало числу символов в каждой строке, мы выводим числа по одному, каждый раз проверяя, не превысила ли общая длина строки заданное число [latex]n[/latex]. Если длина все-таки получается больше, мы выводим то количество символов, которое помещается в данную строку, а остальные отбрасываем.

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

Related Images:

MLoops 7

10/11/2015 by Настя Панько

Задача

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

Два целых числа: количество столбцов и строк.

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

Таблица [latex]m * n[/latex] со следующей закономерностью:

123+123+123+123+1
+123+123+123+123+
3+123+123+123+123
23+123+123+123+12
123+123+123+123+1
+123+123+123+123+
3+123+123+123+123
23+123+123+123+12
123+123+123+123+1
+123+123+123+123+
3+123+123+123+123
23+123+123+123+12
123+123+123+123+1
+123+123+123+123+
3+123+123+123+123
23+123+123+123+12

123+123+123+123+1

+123+123+123+123+

3+123+123+123+123

23+123+123+123+12

123+123+123+123+1

+123+123+123+123+

3+123+123+123+123

23+123+123+123+12

123+123+123+123+1

+123+123+123+123+

3+123+123+123+123

23+123+123+123+12

123+123+123+123+1

+123+123+123+123+

3+123+123+123+123

23+123+123+123+12

Код

 #include <iostream>
 #include <cmath>
 using namespace std;
 
 int main(){
     int m, n;
     cin >> m >> n;
     for (int i = 1; i <= m; i++){
         for (int j = 1; j <= n; j++){
             cout << (abs(1 + 3*i + j) % 4 == 0 ? '+' : (char)('0' + abs(1 + 3*i + j) % 4));
         }
         cout << endl;
     }
     return 0;
 }

#include <iostream>

#include <cmath>

using namespace std;

int main(){

int m, n;

cin >> m >> n;

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

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

cout << (abs(1 + 3*i + j) % 4 == 0 ? '+' : (char)('0' + abs(1 + 3*i + j) % 4));

}

cout << endl;

}

return 0;

}

Тесты

123+
+123
3+12

123+

+123

3+12

123+123
+123+12
3+123+1
23+123+
123+123
+123+12
3+123+1

123+123

+123+12

3+123+1

23+123+

123+123

+123+12

3+123+1

123+123+123
+123+123+12
3+123+123+1
23+123+123+
123+123+123
+123+123+12
3+123+123+1
23+123+123+
123+123+123
+123+123+12
3+123+123+1

123+123+123

+123+123+12

3+123+123+1

23+123+123+

123+123+123

+123+123+12

3+123+123+1

23+123+123+

123+123+123

+123+123+12

3+123+123+1

Решение

Вводим количество строк [latex]m[/latex] и количество столбцов [latex]n[/latex]. Программа имеет два цикла — один внутри другого. Внешний цикл считывает номер строки, а внутренний — обеспечивает сдвиг. Строки и столбцы чередуются со смещением назад по 4 элемента.

Код

Ideone.com

Related Images:

e-olymp 141. Минимальная сумма цифр

10/11/2015 by Антон Локтев

Условие задачи:

Сколько натуральных чисел из промежутка [latex][M,N][/latex] имеют наименьшую сумму цифр ?

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

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

Во входном файле два числа [latex]M[/latex] и [latex]N[/latex] ( [latex]1\le M\le N\le 1000000[/latex] ) .

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

В выходной файл нужно записать ответ — одно число.

Тесты

№	M	N	Вывод
1	1	100	3
2	2	17	1
3	32	1024	2
4	1	1000000	7
5	10	10	1

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

#include <iostream>
using namespace std;

int sumOfDigits(int a){
	int sum = 0;
	while (a > 0){
		sum += a%10;
		a /= 10;
	}
	return sum;
}

int main() {
	int m, n, sumMin, counter = 1;
	cin >> m >> n;
	sumMin = sumOfDigits(m);
	for(int i = m + 1; i <= n; i++){
		if (sumOfDigits(i) < sumMin){
			sumMin = sumOfDigits(i);
			counter = 1;
		}
		else if (sumOfDigits(i) == sumMin)   
		    counter++;
	}
	cout << counter;
	return 0;
}

#include <iostream>

using namespace std;

int sumOfDigits(int a){

int sum = 0;

while (a > 0){

sum += a%10;

a /= 10;

}

return sum;

}

int main() {

int m, n, sumMin, counter = 1;

cin >> m >> n;

sumMin = sumOfDigits(m);

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

if (sumOfDigits(i) < sumMin){

sumMin = sumOfDigits(i);

counter = 1;

}

else if (sumOfDigits(i) == sumMin)

counter++;

}

cout << counter;

return 0;

}

Алгоритм решения

Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму (sumMin) сумме цифр первого числа [latex] M [/latex]. Теперь задаём цикл со счётчиком [latex] i [/latex] от [latex] M + 1 [/latex] до [latex]\le N[/latex]. В случае, когда сумма чисел счётчика меньше сумме цифр числа [latex] M [/latex], присваиваем ей (сумме цифр счётчика i) минимальную сумму цифр и выводим единицу. В противном случае увеличиваем счётчик на единицу и выводим полученный результат. Выводимое число и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.

Код программы можно найти здесь.

Ссылка на полностью засчитанное решение на сайте e-olymp.

Related Images:

MLoop 2

02/11/2015 by Женя Максимова

Задача. Используйте метод хорд для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] все действительные корни уравнения [latex]\frac{x}{2 \cdot \sin x +1}=\tan(\ln(x^2+1))[/latex]. Для подготовки необходимых графиков воспользуйтесь этим ресурсом.

Тесты(найдено с помощью математической системы WolframAlpha):

[latex]A[/latex]

[latex]B[/latex]

[latex]x\approx[/latex]

-20

-11.6945378230838209122818536587051434153…

-1.25741503276862309237205903178504130394…

0.547316310185252929580383582338832450320…

10.9948442206261587135425985750810372810…

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

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

const int max_iterations=100;
const double interval = 0.001;  // interval length for roots subdivision
bool is_root = false;  // is false if function has a second type break in root candidate point
double delta; //precision of root search
double A, B;

double f(double x)//our function
{
 double r = DBL_MAX;
 try
  {
   r =  x / (2*sin(x)+1) - tan(log(x*x+1));  
  }
 catch(...)
  {
   //nothing to do for arithmetic exception
  }
 return r;
}

bool is_change_sign(double fa, double fb)
{
 return fa*fb<0;
}

double find_root(double a, double b, double delta,  bool *yes)
{
 double fa;
 double fb;
 double fc;
 double c;
 int l=0;
 fa=f(a);
 fb=f(b);
 double dy,dy1; //old and new OY projections of chord
 dy=fabs(fa-fb);
 dy1=DBL_MAX;
 while(true)
   {
    l++;
    if(l > max_iterations)
      {
       *yes=false;
       return (a+b)/2;
      }
    c = a - (b - a) * fa/(fb - fa);
    fc = f(c);
    if(fa*fc>0)
      {
       a=c;
       fa=fc;
      }
    else
      {
       b=c;
       fb=fc;
      }
    if(fabs(fa)<delta)
      {
       *yes=true;
       return a;
      }
    if(fabs(fb)<delta)
      {
       *yes=true;
       return b;
      }
    if(l>10) //there's a magic number, we must check conditions of break or stop after some iterations(some = 10)
      {
       if(dy1>dy) //checking if there's break of second kind(pole)
         {
          *yes=false;
          return (a+b)/2;
         }
       if(fabs(b-a)<delta) //else we are near the root
         {
          *yes=true;
          return (a+b)/2;
         }
      }
    dy=dy1; //change old chord height
    dy1=fabs(fa-fb); //calculate new chord height
   }
 // we can't get here
 *yes=false;
 return c;
}

int main()
{
 scanf("%lf %lf %lf",&A,&B,&delta);
 double a,b;
 double fa, fb;
 /*
 test interval for finding roots
 int k=2;
 A= sqrt(exp(M_PI*(1/2.0+k))-1)-M_PI;//70010637.8772-10;
 B= sqrt(exp(M_PI*(1/2.0+k))-1)+M_PI;//70010637.8772+10;
 delta = 1e-12;
 printf("A=%20.19g A=%20.19g delta=%20.19g \n",A,B,delta);
 */
 fb = f(A);
 for(a = A, b = A + interval; b<=B; a += interval, b += interval)
  {
   fa = fb;
   fb = f(b);
   if(is_change_sign(fa,fb))
     {
      double r=find_root(a,b,delta, &is_root);
      if(is_root)
       {
        printf("%14.15lf \n",r);
       }
     }
  }
 return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

#include <stdio.h>

#include <math.h>

#include <iostream>

#include<cfloat>

using namespace std;

const int max_iterations=100;

const double interval = 0.001; // interval length for roots subdivision

bool is_root = false; // is false if function has a second type break in root candidate point

double delta; //precision of root search

double A, B;

double f(double x)//our function

{

double r = DBL_MAX;

try

{

r = x / (2*sin(x)+1) - tan(log(x*x+1));

}

catch(...)

{

//nothing to do for arithmetic exception

}

return r;

}

bool is_change_sign(double fa, double fb)

{

return fa*fb<0;

}

double find_root(double a, double b, double delta, bool *yes)

{

double fa;

double fb;

double fc;

double c;

int l=0;

fa=f(a);

fb=f(b);

double dy,dy1; //old and new OY projections of chord

dy=fabs(fa-fb);

dy1=DBL_MAX;

while(true)

{

l++;

if(l > max_iterations)

{

*yes=false;

return (a+b)/2;

}

c = a - (b - a) * fa/(fb - fa);

fc = f(c);

if(fa*fc>0)

{

a=c;

fa=fc;

}

else

{

b=c;

fb=fc;

}

if(fabs(fa)<delta)

{

*yes=true;

return a;

}

if(fabs(fb)<delta)

{

*yes=true;

return b;

}

if(l>10) //there's a magic number, we must check conditions of break or stop after some iterations(some = 10)

{

if(dy1>dy) //checking if there's break of second kind(pole)

{

*yes=false;

return (a+b)/2;

}

if(fabs(b-a)<delta) //else we are near the root

{

*yes=true;

return (a+b)/2;

}

dy=dy1; //change old chord height

dy1=fabs(fa-fb); //calculate new chord height

}

// we can't get here

*yes=false;

return c;

}

int main()

{

scanf("%lf %lf %lf",&A,&B,&delta);

double a,b;

double fa, fb;

test interval for finding roots

int k=2;

A= sqrt(exp(M_PI*(1/2.0+k))-1)-M_PI;//70010637.8772-10;

B= sqrt(exp(M_PI*(1/2.0+k))-1)+M_PI;//70010637.8772+10;

delta = 1e-12;

printf("A=%20.19g A=%20.19g delta=%20.19g \n",A,B,delta);

fb = f(A);

for(a = A, b = A + interval; b<=B; a += interval, b += interval)

{

fa = fb;

fb = f(b);

if(is_change_sign(fa,fb))

{

double r=find_root(a,b,delta, &is_root);

if(is_root)

{

printf("%14.15lf \n",r);

}

return 0;

}

Алгоритм

Для начала запишем данное нам уравнение в виде функции [latex]y=f(x)[/latex] и построим ее график:

[latex]y=\frac{x}{2 \cdot sin x +1}-tan(ln(x^2+1))[/latex]

Задача о нахождении приближённых значений действительных корней уравнения [latex]f(x)=0[/latex] предусматривает предварительное отделение корня, то есть установление интервала, в котором других корней данного уравнения нет.

Метод хорд предусматривает замену функции на интервале на секущую, и поиск ее пересечения с осью [latex]OX[/latex]. На заданном интервале [latex][a,b][/latex] с точностью [latex]\varepsilon[/latex] корень будет вычисляться согласно итерационному выражению, которое имеет вид:

[latex]x_{i+1}=x_{i-1}-\frac{f(x_{i-1}) \cdot (x_{i}-x_{i-1})}{f(x_{i})-f(x_{i-1}) ) }[/latex]

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

В точке, где находится предполагаемый корень, имеется разрыв второго рода. Здесь метод хорд обнаруживает перемену знака и начинает сужать отрезок. Однако расстояние между крайними точками отрезка не уменьшается, а увеличивается. А именно увеличивается проекция отрезка на ось [latex]OY[/latex]. И чем ближе мы находимся к точке разрыва, тем она больше, а в самой точке стремится к бесконечности. В качестве примера приведем функцию [latex]\frac{(x-5)^2}{x-4}[/latex], имеющую разрыв второго рода в точке [latex]x=4[/latex].
Аналогичный случай — точка разрыва первого рода, где наша хорда стремится к некоторой константе — величине разрыва. Пример — функция [latex]\frac{\sin x\cdot(x-2.5)}{\left | x-2,5 \right |}[/latex], имеющая разрыв первого рода в точке [latex]x=2,5[/latex].
Функция не является разрывной и даже имеет корень, однако в точке корня производная стремится к бесконечности. Например, функция [latex]\sqrt[3]{x-1,2}[/latex], имеющая корень в точке [latex]x=1,2[/latex]. Для функций подобного рода длина проекции отрезка на ось [latex]OY[/latex] будет очень медленно меняться, вследствие чего для разумного числа итераций она будет превосходить заранее выбранную точность [latex]\varepsilon[/latex].

Функция равна нулю или очень близка к нулю на некотором интервале(например, функция [latex]y=rect(x-1,5)\cdot(x-1)\cdot(x-2)^2[/latex]). Здесь метод хорд найдет пересечение с осью [latex]OX[/latex] в интервале, где находятся корни(одна из сторон отрезка будет корнем), но все последующие итерации будут выдавать эту же точку. Поэтому хорда не будет уменьшаться, и даже этот один корень не будет найден(если будет использоваться стандартная [latex]\delta[/latex]-оценка точности по оси [latex]OX[/latex]).

Функция вида [latex]y=x^{2k}[/latex] или ей подобная, например, [latex]y=1+\sin x[/latex], к которой метод хорд вообще не применим, так как нарушается начальное условие применимости этого метода. Здесь нужно ввести дополнительную проверку. Изменим значение функции на небольшую константу — нашу точность [latex]\varepsilon[/latex] и повторим процедуру поиска корней. В результате мы получим [latex]2k[/latex] корней, каждую пару из которых мы можем считать краями интервала, в котором лежит настоящий корень.

К счастью, в данной нам функции присутствует только один из этих случаев, а именно разрыв второго рода. Аналитически рассмотрев нашу функцию, мы обнаружили, что корни следует искать в окрестности точек[latex]\sqrt{e^{\frac{\pi}{2}+\pi \cdot k}-1}[/latex] с отклонением [latex]\pm\pi[/latex]. В корнях функции ее производная быстро растет с ростом [latex]k[/latex].

Критерием отбрасывания кандидата на корень будет рост длины хорды при сужении интервала. Критерием останова будет сужение интервала до заданной точности [latex]\delta[/latex].
Код программы

Related Images:

MLoop 13

31/10/2015 by Настя Ивасенко

Условие

Условие задачи

Вычислите с точностью [latex]\varepsilon[/latex] значение функции [latex]f(x)=\arcsin x[/latex].
При вычислениях допустимо использовать только арифметические операции.

Тесты

№	[latex] x [/latex]	[latex] arcsin x [/latex]
1	-1	-1.56709
2	-0.5	-0.523599
3	0	0
4	0.5	0.523599
5	0.7071067	0.785398
6	0.8660254	1.0472

Решение

Чтобы разложить тригонометрическую функцию только арифметическими операциями, нужно воспользоваться формулами Тейлора.

Ряд Тейлора для функции [latex]\arcsin x[/latex]:

[latex]\arcsin x = \sum_{n=0}^{\infty} \frac{(2n)!}{4^n (n!)^2 (2n+1)} x^{2n+1}[/latex] или:
[latex]\arcsin x = x + \frac{x^3}{6} + \frac{3x^5}{40} + \cdots[/latex]

Вводим переменную, которая будет считать арксинус — [latex]arcsin[/latex].

Так как первый член — [latex]x[/latex], то начальное значение [latex]\arcsin =x[/latex] и [latex]a=x[/latex]. [latex]a[/latex] — это слагаемые суммы, оно будет изменятся с каждым последующим значением [latex]n[/latex].

Теперь нужно узнать на сколько домножать первое слагаемое из ряда Тейлора, чтобы получить второе:

[latex]\frac{(2(n+1))!\cdot x^{2(n+1)+1}}{4^{n+1}((n+1)!)^2 (2(n+1)+1)} \cdot \frac{4^n (n!)^2 (2n+1)}{(2n)!\cdot x^{2n+1}} = \frac{(2n+1)^2 x^2}{2(2n+3)(n+1)}[/latex]

Видно, что эта функция сначала возрастает, а потом убывает ( [latex]x\leq 1[/latex] )
[latex]\frac{(2n+1)^2 x^2}{2(2n+3)(n+1)}[/latex], поэтому [latex]a[/latex] будет уменьшаться. Мы задаем точность [latex]\varepsilon[/latex] и пока [latex]a > \varepsilon[/latex] мы вычисляем сумму
[latex]\arcsin +=a[/latex].

Код

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
	int n=0;
	double x;
	cin >> x; 
	double a=x, arcsin=x, E=0.1e-5;
	while (abs(a*=(x*x*(2*n+1)*(2*n+1)/(2*(n+1)*(2*n+3))))>E) {
		arcsin+=a;
		n++;
	
	}
	cout << arcsin;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n=0;

double x;

cin >> x;

double a=x, arcsin=x, E=0.1e-5;

while (abs(a*=(x*x*(2*n+1)*(2*n+1)/(2*(n+1)*(2*n+3))))>E) {

arcsin+=a;

n++;

}

cout << arcsin;

return 0;

}

Код на ideone

Related Images:

MLoops 4

31/10/2015 by Андрей Яроцкий

Задача:. Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex]m > 0[/latex] (количество строк).

-+-+-*-+-+-*-+-+-*-+-+-*-
+-+-*-+-+-*-+-+-*-+-+-*-+
-+-*-+-+-*-+-+-*-+-+-*-+-
+-*-+-+-*-+-+-*-+-+-*-+-+
+*-+-+-*-+-+-*-+-+-*-+-+-
*-+-+-*-+-+-*-+-+-*-+-+-*
-+-+-*-+-+-*-+-+-*-+-+-*-
+-+-*-+-+-*-+-+-*-+-+-*-+

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

Количество столбцов [latex]n > 0[/latex] и строк [latex]m > 0[/latex].

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

Таблица размером [latex]n[/latex] [latex]\times[/latex] [latex]m[/latex] аналогичная таблице в условии.

Тесты:

№	[latex]n[/latex] [latex]m[/latex]	Таблица
1	1 1	—
2	1 7	— + — + — * —
3	7 1	-+-+-*-
4	10 10	-+-+--+-+ +-+--+-+- -+--+-+- +--+-+-- --+-+--+ -+-+--+- -+-+--+-+ +-+--+-+- -+--+-+- +--+-+--
5	25 8	-+-+--+-+--+-+--+-+-- +-+--+-+--+-+--+-+--+ -+--+-+--+-+--+-+--+- +--+-+--+-+--+-+--+-+ --+-+--+-+--+-+--+-+- -+-+--+-+--+-+--+-+-* -+-+--+-+--+-+--+-+-- +-+--+-+--+-+--+-+--+

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

#include <iostream>
using namespace std;

int main() {
	int n, m;  // Количество столбцов и строк соответственно
	cin >> n >> m;
	for(int i = 0;i < m;i++){             // Цикл для перехода на новую строку
		for(int j = 0;j < n;j++){         // Цикл вычисления номера члена
			if(((i+j+1) % 6 == 0)&&((i+j) != 0)){ // Проверка на кратность шести
				cout << "*";
			}
			else cout << ((i+j+1) % 2 == 0?"+":"-");  // Проверка на кратность двум
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m; // Количество столбцов и строк соответственно

cin >> n >> m;

for(int i = 0;i < m;i++){ // Цикл для перехода на новую строку

for(int j = 0;j < n;j++){ // Цикл вычисления номера члена

if(((i+j+1) % 6 == 0)&&((i+j) != 0)){ // Проверка на кратность шести

cout << "*";

}

else cout << ((i+j+1) % 2 == 0?"+":"-"); // Проверка на кратность двум

}

cout << endl;

}

return 0;

}

Алгоритм решения:

Посмотрев на таблицу можно заметить, что знак «-» выводится когда номер члена последовательности нечетный, знак «+» когда четный и знак «*» когда член последовательности кратный 6. После объявления переменных [latex]n[/latex] и [latex]m[/latex](количество столбцов и строк соответственно) создаем два цикла — один внутри другого. Внешний цикл считает номер строки и, после выполнения внутреннего, переносит последовательность на новую строку. Внутренний цикл считает номер столбца и выполняет проверку на кратность шести, в этом случае выводится знак «*». В противном случае проводится проверка на кратность двум. Если номер члена последовательности кратен двум выводиться знак «+», в противном случае — «-«.

Условие задачи

Код в компиляторе

Related Images:

MLoops 6

31/10/2015 by Максим Носов

Задача

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

Два числа:количество столбцов и строк.

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

Таблица размером n*m со следующей закономерностью:

0+1+0+1+0+1+0+1+0+1+0+1+0
+0+1+0+1+0+1+0+1+0+1+0+1+
1+0+1+0+1+0+1+0+1+0+1+0+1
+1+0+1+0+1+0+1+0+1+0+1+0+
0+1+0+1+0+1+0+1+0+1+0+1+0
+0+1+0+1+0+1+0+1+0+1+0+1+
1+0+1+0+1+0+1+0+1+0+1+0+1
+1+0+1+0+1+0+1+0+1+0+1+0+

0+1+0+1+0+1+0+1+0+1+0+1+0

+0+1+0+1+0+1+0+1+0+1+0+1+

1+0+1+0+1+0+1+0+1+0+1+0+1

+1+0+1+0+1+0+1+0+1+0+1+0+

0+1+0+1+0+1+0+1+0+1+0+1+0

+0+1+0+1+0+1+0+1+0+1+0+1+

1+0+1+0+1+0+1+0+1+0+1+0+1

+1+0+1+0+1+0+1+0+1+0+1+0+

Код

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

int main() {
    int n,m; //задаем переменные(количество столбцов и строк)
    cin>>n>>m; //вводим их
    for(int i=1;i<n+1;i++) { //запускаем цикл по стобцам
        for(int j=1;j<m+1;j++) { //запускаем цикл по строкам
            int k=abs(i-j);
            if ((k%4)==0) cout<<"0"; //задаем условие, согласно с закономерностью
            else if ((k%2)==0) cout<<"1";
            else cout<<"+";
        }
        cout<<endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n,m; //задаем переменные(количество столбцов и строк)

cin>>n>>m; //вводим их

for(int i=1;i<n+1;i++) { //запускаем цикл по стобцам

for(int j=1;j<m+1;j++) { //запускаем цикл по строкам

int k=abs(i-j);

if ((k%4)==0) cout<<"0"; //задаем условие, согласно с закономерностью

else if ((k%2)==0) cout<<"1";

else cout<<"+";

}

cout<<endl;

}

return 0;

}

Решение

Для того, чтобы решить поставленную задачу, нужно сначала понять закономерность чередования символов в таблице. Каждый символ имеет свой номер столбца([latex]n[/latex]) и строки([latex]m[/latex]). Запускаем первый цикл для столбцов, в нем вложенный цикл по строкам. Используя «счетчики» в циклах ([latex]i[/latex] и [latex]j[/latex]) задаем условия, учитывая закономерность. Закономерность такая, что в каждой новой строке «0» сдвигается вправо на позицию [latex]i=j[/latex] , а остальные элементы «подстраиваются под » «0». Таким образом, » 1″ задаем по формуле [latex]|i-j|%2==0[/latex], «0» задаем по формуле [latex]|i-j|%4==0[/latex], а «+» остаются все остальные. После того как цикл по строкам заканчивается — ставим переход на новую строку.

Ссылка на код.

Related Images:

MLoops2

31/10/2015 by Алина Гончарова

Задача

Найти закономерность и написать программу, которая выводит аналогичную таблицу для любых чисел $n > 0$ (количество столбцов) и $m > 0$ (количество строк).

-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*

Решение

Для того, чтобы решить поставленную задачу, нужно сначала понять закономерность чередования символов — и * в таблице. Каждый символ имеет свой номер строки([latex]m[/latex]) и столбца([latex]n[/latex]), а чтобы определить их номера зададим счетчики [latex]i[/latex] и [latex]j[/latex]. Задача состоит из того, что нужно определить закономерность появления символа [latex]-[/latex], в остальных случаях нужно выводить символ [latex]*[/latex]. Символ [latex]-[/latex] чередуется с символом [latex]*[/latex], и поэтому можно увидеть, что этот символ [latex]-[/latex] ставится на место, при котором сумма номеров столбцов и строк делится нацело на 2. Решить данную задачу можно с помощью тернарной операции.

Код

#include <iostream>
using namespace std;

int main() {
	int m, n;
	cin >> m >> n;
	for (int i=1; i<n; i++){
		for (int j=1; j<m; j++){
			cout << ((i+j)%2==0? "-":"*");
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int m, n;

cin >> m >> n;

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

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

cout << ((i+j)%2==0? "-":"*");

}

cout << endl;

}

return 0;

}

Тесты

Входные данные	10 10	8 5	25 8
Выходные данные	-----* ----- ----- ----- ----- ----- ----- ----- ----- ----*-	---- ---- ---- ---- ----	------------- ------------* ------------- ------------* ------------- ------------* ------------- ------------*

Задача взята отсюда.

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

Related Images:

Mloops 5

30/10/2015 by Антон Локтев

Условие задачи

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex] n>0 [/latex] (количество столбцов) и [latex] m>0 [/latex] (количество строк): +++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*++ .

Задача находится здесь.

Тесты

№	n	m	Таблица
1	25	8	+++++++++++++++++++++ +++++++++++++++++++++ +++++++++++++++++++++ +++++++++++++++++++++ +++++++++++++++++++++ ++++++++++++++++++++* +++++++++++++++++++++ +++++++++++++++++++++
2	6	6	+++++* +++++ +++++ +++++ +++++ *+++++
3	2	5	++ ++ ++ ++ +*

Алгоритм решения

Таблица, которую необходимо вывести на экран представляет собой определённую последовательность. Каждый символ таблицы имеет номера столбца и строки (нумерация от 0 до n или m не включительно). Для этого задаём счётчики [latex] i [/latex] и [latex] j [/latex] . Наша задача — определить закономерность появления символа [latex] \ast [/latex] в данной таблице, поскольку в иных случаях необходимо вывести символ [latex] + [/latex]. В первой строке «звёздочка» встречается в данной таблице в [latex] 6,12,18,24[/latex] столбцах. Во второй строке «звёздочка» находится в [latex] 5,11,17,23[/latex] столбцах. В последующих строках ситуация аналогичная. Можно заметить, что символ [latex] \ast [/latex] стоит на позициях, при которых сумма номера строки и номера столбца делится нацело на 6. Проверяем это условие с помощью тернарной операции:

cout << ((i+j-5)%6== 0? "*":"+");

1	cout << ((i+j-5)%6== 0? "*":"+");

от суммы номеров столбца и строки отнимаем число [latex] 5 [/latex], поскольку нам необходимо, чтобы первыми пятью символами последовательности были плюсы.

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

#include <iostream>
using namespace std;

int main() {
	int n,m;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cout << ((i+j-5)%6== 0? "*":"+");
		}
	cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,m;

cin >> n >> m;

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

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

cout << ((i+j-5)%6== 0? "*":"+");

}

cout << endl;

}

return 0;

}

Ссылка на рабочий код программы находится здесь.

Related Images:

MLoop 4

15/10/2015 by Настя Панько

Задача. Вычислите с точностью [latex]\epsilon[/latex] значение функции [latex]f\left( x \right) = \sin x[/latex]. При вычислениях допустимо использовать только арифметические операции.

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

#include <iostream>
#include <cmath>
using namespace std;
double sin (double x, double e) {
     double k, a = x;
     double s = x;
     int n=1;
     while (abs(a) > e) {
	   k = - x * x / (2 * n * (2 * n + 1));
	   a *= k;
	   s += a;
	   n++;
     }
     return s;
}
int main () {
      double x, e;
      cin >> x >> e;
      cout << endl << sin(x, e);
}

#include <iostream>

#include <cmath>

using namespace std;

double sin (double x, double e) {

double k, a = x;

double s = x;

int n=1;

while (abs(a) > e) {

k = - x * x / (2 * n * (2 * n + 1));

a *= k;

s += a;

n++;

}

return s;

}

int main () {

double x, e;

cin >> x >> e;

cout << endl << sin(x, e);

}

Тесты

Входные данные	Входные данные	Выходные данные
x	e	sin(x)
1	0,01	0,841471
3	0,01	0,14112
4	0,001	-0,756802
7	0,0001	0, 656987

Решение

Необходимо использовать формулу Тейлора, а именно ряд Маклорена, чтобы представить функцию

[latex]f(x)[/latex] = [latex]\sin x[/latex]

Эта формула имеет такой вид [latex]\sin x[/latex] = [latex]\sum _ { n=0 }^{ \infty }{ { (-1) }^{ n } } \frac { { x }^{ 2n+1 } }{ (2n+1)! }[/latex].

Подключаем заголовочный файл cmath для использования функции abs(). Построим реккурентную формулу для [latex]x_n[/latex] через [latex]x_{n-1}[/latex] для [latex]n > 1 \left(x_0=x\right)[/latex]. Для этого найдем отношение последующего члена ряда к предыдущему [latex]k = \frac{x_n}{x_{n-1}} = -\frac{x^2}{2n\cdot(2n + 1)}[/latex].

Используем функцию while, чтобы проверить является ли член ряда [latex]x_n[/latex] больше [latex]e[/latex].

Ideone.com

Related Images:

e-olymp 7338. Постоянная сумма цифр

30/09/2015 by Максим Носов

Задача

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

В единственной строке задано целое одно цифровое число.

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

Количество чисел.

Код

#include <iostream>
using namespace std;

int main() {
    int n,a,b,c,k=0;  // задаем переменные
    cin>>n; //вводим число, на которое будут умножаться все двухзначные числа
    for (int i=10;i<=99;i++) {  //задаем цикл от 10 до 99(все двухзначные числа)
        c=i*n;  //для удобства задаем переменную с - произведение двухзначного числа и заданного нами одно цифрового
        a=i/10+i%10; //задаем переменную а - сума цифр двухзначного числа
        b=(c/10)%10+c%10+c/100;   // и вычисляем сумму цифр числа с
        if (a==b) k++;  //если  суммы чисел а и с равны то добавляем 1 на "счетчик"
    }
    cout<<k;  //выводим на экран количество чисел 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,a,b,c,k=0; // задаем переменные

cin>>n; //вводим число, на которое будут умножаться все двухзначные числа

for (int i=10;i<=99;i++) { //задаем цикл от 10 до 99(все двухзначные числа)

c=i*n; //для удобства задаем переменную с - произведение двухзначного числа и заданного нами одно цифрового

a=i/10+i%10; //задаем переменную а - сума цифр двухзначного числа

b=(c/10)%10+c%10+c/100; // и вычисляем сумму цифр числа с

if (a==b) k++; //если суммы чисел а и с равны то добавляем 1 на "счетчик"

}

cout<<k; //выводим на экран количество чисел

return 0;

}

Тесты

№	Входные данные	Выходные данные
1	2	10
2	0	0
3	1	90
4	9	6
5	5	10

Решение

Для начала задаем переменные и вводим с клавиатуры число, на которое будут умножаться все двухзначные числа. Задаем цикл от 10 до 99. Для удобства вводим переменную [latex]c[/latex], которая равна произведению двухзначного числа на входное число и переменную [latex]a[/latex], которая равна сумме цифр входного числа. Далее находим сумму цифр числа с — [latex](c/10)%10+c%10+c/100[/latex]. Если сумма цифр входного числа равна сумме цифр [latex]c[/latex], то добавляем 1 на «счетчик». В конце выводим на экран количество чисел, которые не меняют свою сумму цифр при умножении на число, которое мы ввели с клавиатуры.

Ссылку на код здесь.

Задача взята с сайта.

Related Images:

e-olymp 388. Превращение

30/09/2015 by Молоканов Юрий

Условие

Возьмем какое-нибудь натуральное число [latex]N[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на [latex]2[/latex], если нечетное, прибавим [latex]1[/latex]. После нескольких таких изменений мы всегда получаем число [latex]1[/latex]. Например, из числа [latex]11[/latex] получается число [latex]12[/latex], затем [latex]6[/latex], [latex]3[/latex], [latex]4[/latex], [latex]2[/latex] и, наконец, [latex]1[/latex]. Таким образом, для получения [latex]1[/latex] из [latex]11[/latex] нужно проделать [latex]6[/latex] изменений.

Напишите программу, которая считывает натуральное число и выводит количество изменений данного числа до получения [latex]1[/latex].

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

№	Входные данные	Выходные данные
1	1	0
2	11	6
3	65	13
4	1024	10

Код

#include <iostream>
using namespace std;

int main() {
	int n, i;	// n для числа, i для счета преобразований
	cin >> n;
	for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2);	// Преобразовываем n, пока не получим 1
	cout << i;	// Выводим значение счетчика
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, i; // n для числа, i для счета преобразований

cin >> n;

for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); // Преобразовываем n, пока не получим 1

cout << i; // Выводим значение счетчика

return 0;

}

Решение

Так как в качестве ответа на задачу нам нужно вывести значение переменной-счетчика, которая отвечает за количество проделанных изменений, то объявлять ее нужно будет не в начальных условиях цикла for, а в пределах главной функции:

#include <iostream>
using namespace std;

int main() {
	int n, i;	// n для числа, i для счета преобразований

#include <iostream>

using namespace std;

int main() {

int n, i; // n для числа, i для счета преобразований

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

Цикл начинается со значением счетчика 0, так как возможны случаи, когда операций над [latex]n[/latex] вообще не нужно будет производить (конкретно — при [latex]n=1[/latex]).
Поскольку нам гарантируют, что входное число [latex]n[/latex] — натуральное, то цикл будет работать до тех пор, пока [latex]n>1[/latex].
После каждой итерации значение счетчика будет увеличено на [latex]1[/latex].
Тело цикла состоит из единственного оператора присваивания переменной с числом [latex]n[/latex] нового значения. [latex]n[/latex] может быть преобразовано двумя способами, и для определения нужного используется проверка на его четность:
- если [latex]n[/latex] — нечетное, то значение [latex]n[/latex] увеличивается на [latex]1[/latex];
- в противном случае [latex]n[/latex] делится на [latex]2[/latex].

Реализуем описанный алгоритм, после которого отправляем на печать значение счетчика i:

for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2);
cout << i;

1 2	for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); cout << i;

Ссылки

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

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

Подтверждение решения на E-Olymp.

Related Images:

e-olimp 7365. Молоко и пирожок

30/09/2015 by Настя Ивасенко

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Тесты

Количество детей	Вес	Количество упаковок молока	Количество пирожков
3	30 29 30	1	1
5	25 41 56 20 20	1	3
4	30 30 30 30	0	0
7	25 26 27 28 29 23 24	2	7

Код

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

int main() {
    int p=0; //пирожки
    int n, k; //количество детей, вес и упаковки молока
    double m, u, w; 
    cin >> n;
    m=0.2; u=0.9;
    for(int i=0; i<n; i++) {
        cin >> w;
        if (w<30) p++;
        if(w>=30) p=p+0;
    }
    k= ceil(p*m/u);
    cout << k << " " << p;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int p=0; //пирожки

int n, k; //количество детей, вес и упаковки молока

double m, u, w;

cin >> n;

m=0.2; u=0.9;

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

cin >> w;

if (w<30) p++;

if(w>=30) p=p+0;

}

k= ceil(p*m/u);

cout << k << " " << p;

return 0;

}

Решение

Возьмем количество пирожков за счетчик. Используя for найдем количество пирожков для детей, вес которых не превышает 30кг.

По количеству пирожков мы можем найти количество упаковок молока. При этом мы можем получить не целое число. Чтобы избежать этого, подключаем библиотеку <cmath> и используем округление вверх ceil .

Посмотреть код на ideone можна здесь.

Проверить правильность на e-olimp можна здесь.

Related Images:

e-olymp 109. Нумерация

22/09/2015 by Сплошнов Кирилл

Задача взята с сайта e-olymp.com.

Условие

Для нумерации [latex]M[/latex] страниц книги использовали [latex]N[/latex] цифр. По заданному [latex]N[/latex] вывести [latex]M[/latex] или [latex]0[/latex], если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число [latex]N[/latex]. В книге не более [latex]1001[/latex] страницы.

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

Искомое количество страниц.

Тесты :

N	8	21	22	113	999	1001
M	8	15	0	61	369	0

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

#include <iostream>
using namespace std;

int main()
{
	int N;
	cin >> N;
	for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i
    {
		if (i < 10) // в i одна цифра
			N --;
		else if (i >= 10 && i < 100) // 2 цифры
			N -= 2;
		else if (i >= 100 && i < 1000) // 3 цифры
			N -= 3;
		else  // 4 цифры
			N -= 4;
		if (N == 0) // если лишних цифр у нас не осталось
		{
			cout << i << endl;
			break;
		}
		else if (N < 0) // иначе выводим "0"
		{
			cout << 0 << endl;
			break;
		}
    }
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int N;

cin >> N;

for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i

{

if (i < 10) // в i одна цифра

N --;

else if (i >= 10 && i < 100) // 2 цифры

N -= 2;

else if (i >= 100 && i < 1000) // 3 цифры

N -= 3;

else // 4 цифры

N -= 4;

if (N == 0) // если лишних цифр у нас не осталось

{

cout << i << endl;

break;

}

else if (N < 0) // иначе выводим "0"

{

cout << 0 << endl;

break;

}

return 0;

}

Примечание

Общее (и более компактное) решение можно написать, подключив библиотеку <cmath> и воспользовавшись функцией логарифма с основанием 10.

Код программы (вторая версия)

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
	int N;
	cin >> N;
	for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i
    {
		N -= floor(log10(i) + 1);
		if (N == 0) // если лишних цифр у нас не осталось
		{
			cout << i << endl;
			break;
		}
		else if (N < 0) // иначе выводим "0"
		{
			cout << 0 << endl;
			break;
		}
    }
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int N;

cin >> N;

for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i

{

N -= floor(log10(i) + 1);

if (N == 0) // если лишних цифр у нас не осталось

{

cout << i << endl;

break;

}

else if (N < 0) // иначе выводим "0"

{

cout << 0 << endl;

break;

}

return 0;

}

Ссылки

Засчитанное решение на e-olymp.com .

Рабочий код на Ideone.com .

Related Images:

e-olymp 128. Счастливые билеты

21/09/2015 by Женя Максимова

Задача. Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N(N \leq 27)[/latex].

Счастливым билетом называется билет с шестизначным номером, у которого сумма первых трёх цифр равна сумме трёх последних.

Тесты

Число [latex]N[/latex]	3	27	26	1	10
Количество билетов	100	1	9	9	3969

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

#include <iostream>
using namespace std;
int main() 
{
  int N, c = 0;
  cin >> N;
  for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа
  {
     for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры
     {
        if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры
        { c++; } //подсчет подходящих номеров
     }
  }
  cout << c*c; //увеличение количества в c раз для шестизначного числа
  return 0;
}

#include <iostream>

using namespace std;

int main()

{

int N, c = 0;

cin >> N;

for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа

{

for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры

{

if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры

{ c++; } //подсчет подходящих номеров

}

cout << c*c; //увеличение количества в c раз для шестизначного числа

return 0;

}

Алгоритм

Любой шестизначный номер мы можем представить как 2 трехзначных номера.

Рассмотрим все варианты трехзначных номеров. Две первые цифры такого номера могут быть любыми. Переберем все их комбинации с помощью двух вложенных циклов. Для третьей цифры введем специальное условие. Она должна быть результатом вычитания двух первых цифр из [latex]N[/latex], а также быть именно цифрой, то есть меньшей 10.

Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c \cdot c[/latex].

Решение

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

Related Images:

А694а

14/09/2015 by Сабиров Ильдар

Задача: Получить квадратную матрицу порядка [latex]n[/latex] [latex]\begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}[/latex]

Тесты:

n	Матрица
3	1 0 0 0 1 0 0 0 1
4	1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
6	1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
    int m[n][n];
    for(int i=0;i<n;i++)
    {
    	m[i][i]=1;
    }
    for(int i=0;i<n;i++)
    {
    	for(int y=0;y<n;y++)
        {
    	    if(m[i][y]!=1)
    	    {
    		    m[i][y]=0;
    	    }
        }
    }
    for(int i=0;i<n;i++)
    {
    	for(int y=0;y<n;y++)
        {
        	cout<<m[i][y]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}