Category Archives: 3. Циклы

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

Циклы

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

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

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

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

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

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

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 10

08/11/2015 by Катя Писова

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

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

Для нахождения значения функции $f\left( x \right) = \text{ch}x$ (гиперболический косинус) с точностью [latex]\varepsilon[/latex] воспользуемся формулой Тейлора (разложение функции в бесконечную сумму степенных функций):[latex]chx=1+\frac{x^2}{2}+\frac{x^4}{4}+[/latex]…[latex]=\sum_{n=0}^{\infty}\frac{1}{(2n+1)!}\times x^{2n}[/latex]. [latex]x_n=\frac{1}{(2n+1)!}\times x^{2n}[/latex], тогда [latex]x_{n-1}=\frac{1}{(2(n-1)+1)!}\times x^{2(n-1)}[/latex]. Рекуррентное соотношение [latex]x_n[/latex] и [latex]x_{n-1}=[/latex][latex]\frac{x_n}{x_{n-1}}=\frac{x^2}{2n\times(2n-1)}[/latex].

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

#include <iostream>
#include <cmath>
using namespace std;
 
double ch(double x, double e)
{
	double result = 1;
	double member = 1;
	for (int i = 1; abs(member) >= e; i++)
	{
		member *= x * x;
		member /= 2*i * (2*i - 1);
		result += member;
	}
	return result;
}
 
int main() 
{ 
	double x, e;
	cin >> x >> e;
	cout << ch(x, e);
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double ch(double x, double e)

{

double result = 1;

double member = 1;

for (int i = 1; abs(member) >= e; i++)

{

member *= x * x;

member /= 2*i * (2*i - 1);

result += member;

}

return result;

}

int main()

{

double x, e;

cin >> x >> e;

cout << ch(x, e);

return 0;

}

Тесты:

Входные данные		Выходные данные
x	e	ch(x)
9	0.01	4051.54
16	0.0001	4.44306e+06
0.85	0.00001	1.38353
0.11	0.001	1.00606

Здесь можно посмотреть решение задачи на ideone.com

Related Images:

MLoops8

07/11/2015 by Настя Филипчук

Задача

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

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

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

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

+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21

Код

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

#include <iostream>

using namespace std;

int main(){

int m,n;

cin>>n>>m;

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

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

if(i%2==0){

if ((j+3)%4==0)

cout<< "1";

else

cout<<(j%4==0?"2":"+");

}

else{

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

cout<<"1";

else

cout<<((j+2)%4==0?"2":"+");

}

cout<<endl;

}

return 0;

}

Упрощенный вариант

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

#include <iostream>

using namespace std;

int main()

{

int m,n;

cin>>n>>m;

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

{

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

{

if( ((i%2==0) && ((j+3)%4==0))||((i%2!=0) && ((j+1)%4==0)))

{

cout<< "1";

}

if ((j+3-2*(i%2))%4!=0)

{

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

}

cout<<endl;

}

return 0;

}

Тесты

[latex]n[/latex]	[latex]m[/latex]	Выходные данные
1	1	+
7	7	+21++21 1++21++ +21++21 1++21++ +21++21 1++21++ +21++21
15	6	+21++21++21++21 1++21++21++21++ +21++21++21++21 1++21++21++21++ +21++21++21++21 1++21++21++21++
25	8	+21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21

Решение

Для решения сначала нужно найти закономерность чередования символов в таблице. Пусть нумерация столбцов и строк будет начинаться с единицы, тогда, если строка [latex]i \vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 1 кратен 4 ([latex] (j+1)\vdots 4 [/latex]), то в данной строке и столбце находится «1», если же результат от прибавления номера столбца к 2 кратен 4([latex] (j+2)\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Если же строка [latex]i\vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 3 кратен 4 ([latex] (j+3)\vdots 4[/latex]), то в данной строке и столбце находится «1», а если номер столбца кратен 4([latex] j\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Ссылки

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

Упрощенный код

Related Images:

MLoop 11

04/11/2015 by Павел Загинайло

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

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

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

#include <iostream>
#include <cmath>
#define PI 3.1415926
using namespace std;

double f(double e, double x){
	int i = 0;
	double p = x;
	double s = x;
	while (p > e){
		p*=(x*x*(2*i + 1)*(2*i + 1))/(2*(i+1)*(2*i + 3));
		s+=p;
		i++;
	}
	return s;
}

int main() {
	double e; //точность
	double x;
	cin >> e >> x;
	cout << PI/2 - f(e, x) << endl;
	return 0;
}

#include <iostream>

#include <cmath>

#define PI 3.1415926

using namespace std;

double f(double e, double x){

int i = 0;

double p = x;

double s = x;

while (p > e){

p*=(x*x*(2*i + 1)*(2*i + 1))/(2*(i+1)*(2*i + 3));

s+=p;

i++;

}

return s;

}

int main() {

double e; //точность

double x;

cin >> e >> x;

cout << PI/2 - f(e, x) << endl;

return 0;

}

Тесты

Входные данные		Выходные данные	Арккосинус
e	x	arccos = ([latex]\pi[/latex]/2 — f)	Арккосинус
0.000001	0.866	0.523651	0.5236495809
0.01	0.5	1.04727	1.0471975512
0.00000000000001	0.35	1.21323	1.2132252231
0.00001	0.99	0.141873	0.1415394733

Решение

Для того, чтобы представить функцию $f\left( x \right) = \arccos x$ необходимо воспользоваться формулой Тейлора, а именно рядом Маклорена для арккосинуса. Она имеет следующий вид:

[latex]\arccos x=\frac{\pi}{2}-\sum_{n=1}^\infty\frac{(2n)!}{4^{n}(n!)^{2}(2n+1)}x^{2n+1}[/latex]

Чтобы при вычислениях использовать только арифметические операции необходимо преобразовать это выражение. Первый член данной суммы — [latex]x[/latex]. Нужно узнать на что нужно домножить первый элемент, чтобы получить следующий. Для этого следует найти, чему будет равно отношение [latex]\frac{a_{n+1}}{a_{n}}[/latex]. В результате мы получим следующее: [latex]\frac{x^{2}(2n+1)^{2}}{2(n+1)(2n+3)}[/latex].

В функции [latex]f[/latex] переменная [latex]p[/latex] — слагаемые нашей суммы, а изначально — первый элемент. Также, в начале мы присвоили переменной суммы значение первого элемента. Затем в цикле мы домножаем наше слагаемое на полученный ранее коэффициент и складываем его с суммой до тех пор, пока значение [latex]p[/latex] превышает значение заданной точности [latex]e[/latex]. В основной части программы мы лишь выводим разность [latex]\pi/2[/latex] и нашей суммы. Это и будет значение арккосинуса.

Код на ideone.com

Related Images:

MLoops1

03/11/2015 by Кирилл Демиденко

Задача

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

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

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

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

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

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

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

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

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

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

Тесты

Ввод:	6 6	8 4	25 8
Вывод:	---* --- --- --- --- --*-	---- ---- ---- ----	------------- ------------* ------------- ------------* ------------- ------------* ------------- ------------*

Решение

Что бы решить задачу, надо написать программу, которая выводит поочередное появления символов — и * . Каждый символ имеет номер строки и номер столбца, и что бы их считывать зададим [latex] i [/latex] , [latex] j [/latex] . Когда число столбцов четное, то новая строка будет начинаться с того же символа, с которого закончилась предыдущая. Поэтому, что бы получить наше условие, нам надо задать нечетное количество столбцов.

#include <iostream>
using namespace std;

int main() {
    int m,n;
    cin >> m >> n;
    for (int i=0;i<n;i++){ 
        for (int j=0;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=0;i<n;i++){

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

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

}

cout << endl;

}

return 0;

}

Ссылка на ideone

Related Images:

MLoop 12

02/11/2015 by Таня Корнилова

Задача. MLoop 12

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

Тесты

Входные данные			Выходные данные
№	Точность	Аргумент	[latex]\arctan x[/latex]	Погрешность
1	1	0.5	0.5	0.0363524
2	10	0.82	0.669293	0.0175249
3	100	0.77	0.652823	0.00335552
4	1000	1	0.666667	0.118731

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

#include <iostream>
#include <cmath>
using namespace std;
 
double myAtan(double x, int n) {
	double a = x;
	double sum = a;
	double b = a;
	double E = 1 / n;
	for(int i = 1; a > E; i++){
		b *= - x * x;
		a *= b / (2 * i + 1);
		sum += a;
	}
	return sum;
}
 
int main() {
	double x;
	int n;
	cin >> x >> n;
	cout << "my arctg: " << myAtan(x, n) << endl;
    cout << "arctg: " << atan(x) << endl;
    cout << "|arctg - my arctg| = " << abs(myAtan(x, n) - atan(x)) << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double myAtan(double x, int n) {

double a = x;

double sum = a;

double b = a;

double E = 1 / n;

for(int i = 1; a > E; i++){

b *= - x * x;

a *= b / (2 * i + 1);

sum += a;

}

return sum;

}

int main() {

double x;

int n;

cin >> x >> n;

cout << "my arctg: " << myAtan(x, n) << endl;

cout << "arctg: " << atan(x) << endl;

cout << "|arctg - my arctg| = " << abs(myAtan(x, n) - atan(x)) << endl;

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

Для того, чтобы найти приблизительное значение [latex]\arctan x[/latex] возпользуемся формулой ряда Тейлора: [latex]\arctan x = x — \frac{x^3}{3} + \frac{x^5}{5} -[/latex] … [latex]= \sum_{n=0}^{\infty}\frac{(-1)^n}{2n+1}\cdot x^{2n+1}[/latex] для всех [latex]|x| \le 1[/latex]. Представим каждый член суммы как [latex]a_n = \frac{(-1)^n\cdot a^{2n+1}}{2n+1}[/latex], и будем рекурсивно вычислять числитель данной дроби [latex]m_n = m_{n-1} \cdot (- a^2)[/latex]. Тогда, будем находить значение очередного члена ряда по формуле [latex]a_n = \frac{m_n}{2n + 1}[/latex], пока [latex]a_n > \frac{1}{\varepsilon}[/latex].

Related Images:

MLoop 3

02/11/2015 by Таран Таня

Используйте метод золотого сечения для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] локальный максимум функции $f\left( x \right) = \ln \left(1+ x^{2} - \cos x \right) - e^{\sin \pi x}$ на отрезке $\left[a;b\right]$ .

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

[latex]a, b[/latex] — концы отрезка, на котором требуется найти максимум, и точность [latex]\varepsilon[/latex].

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

Точка локального максимума и локальный максимум в формате [latex](x_{max}, y_{max})[/latex].

Тесты

[latex]\varepsilon[/latex]	[latex]a[/latex]	[latex]b[/latex]	[latex](x_{max}, y_{max})[/latex]
[latex]0.001[/latex]	[latex]1.05[/latex]	[latex]2.2[/latex]	[latex](1.74435, 0.951781)[/latex]
[latex]0.0001[/latex]	[latex]1.05[/latex]	[latex]2.2[/latex]	[latex](1.74417, 0.951781)[/latex]
[latex]0.0001[/latex]	[latex]5.7[/latex]	[latex]8[/latex]	[latex](7.57498, 3.68407)[/latex]
[latex]0.0001[/latex]	[latex]3[/latex]	[latex]4[/latex]	[latex](3.61901, 2.31289)[/latex]

Алгоритм

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

[latex]D(f) = x^2 + 1 + \cos x > 0 [/latex]
[latex]D(f) = x^2 + 1 + \cos x = x^2 + [/latex] [latex]\frac{1}{2}[/latex] [latex] \cos^2[/latex] [latex]\frac{x}{2}[/latex] [latex] > 0[/latex] [latex]\forall[/latex] [latex]x[/latex] [latex]\in [/latex] [latex] \mathbb{R}[/latex]

Таким образом, функция определена на всей числовой оси и мы имеем право рассматривать функцию для любого значения аргумента (также это видно по графику).
Однако следует помнить о том, что используемый нами метод золотого сечения принадлежит к группе симметричных методов и накладывает некоторые ограничения на исследуемую функцию. Применимость данного метода гарантируется только для непрерывных, унимодальных функций.
Унимодальная функция — это функция, которая монотонна на обе стороны от точки максимума [latex]x_{max}[/latex].

[latex]x_1 \le[/latex] [latex]x_2 \le[/latex] [latex]x_{max}[/latex] [latex]\Rightarrow[/latex] [latex]f(x_1) \le[/latex] [latex]f(x_2) \le[/latex][latex]f(x_{max})[/latex]
[latex]x_1 \ge[/latex] [latex]x_2 \ge[/latex] [latex]x_{max}[/latex] [latex]\Rightarrow[/latex] [latex]f(x_1) \le[/latex] [latex]f(x_2) \le[/latex][latex]f(x_{max})[/latex]

Отсюда следует, что если функция [latex]f(x)[/latex] унимодальна на отрезке [latex][a; b][/latex], то максимум этой функции единственен, а локальные минимумы обязательно располагаются на его концах. Так как данная нам функция не является таковой, то для корректного применения метода и получения желаемого результата мы будем собственноручно задавать такие отрезки, на которых представленная функция унимодальна (их несложно выделить по графику).

Проведя анализ функции, обратимся к самому методу золотого сечения.

Для того чтобы найти определенное значение функции на заданном отрезке, отвечающее заданному критерию поиска (в нашем случае максимум), рассматриваемый отрезок требуется поделить в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки [latex]x_1[/latex] и [latex]x_2[/latex] такие, что

[latex]\frac{b — a}{b — x_1}[/latex] [latex]= \frac{b — a}{x_2 — a} =[/latex] [latex]\varphi[/latex] [latex] = \frac{1 + \sqrt{5}}{2}[/latex]

То есть точка [latex]x_1[/latex] делит отрезок [latex][a; x_2][/latex] в отношении золотого сечения. Аналогично [latex]x_2[/latex] делит отрезок [latex][x_1; b][/latex] в той же пропорции. Для нахождения максимума выполняем следующую последовательность действий:

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

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

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

const double goldenRatio = (1 + sqrt(5)) / 2; // "Золотое" число

// Рассматриваемая нами функция
double function(double x) {
	return log(1 + x * x - cos(x)) - pow(M_E, sin(M_PI * x));
}

int main() {
	double a, b; // Концы отрезка
	double accuracy; // Точность, с которой мы находим локальный максимум
	double x1, x2; // Точки, делящие текущий отрезок в отношении золотого сечения
	cin >> a >> b >> accuracy;
	while (fabs(b - a) > accuracy) {
		   x1 = b - (b - a) / goldenRatio; 
	       x2 = a + (b - a) / goldenRatio;
	       if (function(x1) <= function(x2)) // Условие для поиска максимума
	           a = x1; 
	       else 
	           b = x2;
	} // Выполняем, пока не достигнем заданной точности
	cout << "(" << (a + b) / 2 << ", " << function((a + b) / 2) << ")"; 
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

const double goldenRatio = (1 + sqrt(5)) / 2; // "Золотое" число

// Рассматриваемая нами функция

double function(double x) {

return log(1 + x * x - cos(x)) - pow(M_E, sin(M_PI * x));

}

int main() {

double a, b; // Концы отрезка

double accuracy; // Точность, с которой мы находим локальный максимум

double x1, x2; // Точки, делящие текущий отрезок в отношении золотого сечения

cin >> a >> b >> accuracy;

while (fabs(b - a) > accuracy) {

x1 = b - (b - a) / goldenRatio;

x2 = a + (b - a) / goldenRatio;

if (function(x1) <= function(x2)) // Условие для поиска максимума

a = x1;

else

b = x2;

} // Выполняем, пока не достигнем заданной точности

cout << "(" << (a + b) / 2 << ", " << function((a + b) / 2) << ")";

return 0;

}

Ссылки

Код программы
Больше информации о методе золотого сечения:
Источник 1; Источник 2; Источник 3;

Related Images:

MLoops 14

02/11/2015 by Александр Коломеец

MLoops14.

Постановка задачи

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

123...k123...k123...k123...k
++++++1++++++1++++++1++++++1
++++++2++++++2++++++2++++++2
++++++3++++++3++++++3++++++3
++++++.++++++.++++++.++++++.
++++++.++++++.++++++.++++++.
++++++.++++++.++++++.++++++.
++++++k++++++k++++++k++++++k
123...k123...k123...k123...k
++++++1++++++1++++++1++++++1
++++++2++++++2++++++2++++++2

123...k123...k123...k123...k

++++++1++++++1++++++1++++++1

++++++2++++++2++++++2++++++2

++++++3++++++3++++++3++++++3

++++++.++++++.++++++.++++++.

++++++k++++++k++++++k++++++k

123...k123...k123...k123...k

++++++1++++++1++++++1++++++1

++++++2++++++2++++++2++++++2

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

Легко заметить, что строки с номерами [latex]1 + i \left( k + 1 \right), i \in \mathbb{N}_0[/latex] состоят из натуральных чисел от 1 до k. Также в таблице есть столбцы, совпадающие с первой строкой. Все остальные клетки заполнены символом «+».

Тесты

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

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

[latex]n[/latex]

[latex]m[/latex]

[latex]k[/latex]

1
1

11111

121
+1+
+2+
121

121

+1+

+2+

121

1234123412
+++1+++1++
+++2+++2++
+++3+++3++
+++4+++4++
1234123412
+++1+++1++
+++2+++2++
+++3+++3++
+++4+++4++

1234123412

+++1+++1++

+++2+++2++

+++3+++3++

+++4+++4++

1234123412

+++1+++1++

+++2+++2++

+++3+++3++

+++4+++4++

123456789101112345678910111234567
++++++++++++1++++++++++++1+++++++
++++++++++++2++++++++++++2+++++++
++++++++++++3++++++++++++3+++++++
++++++++++++4++++++++++++4+++++++
++++++++++++5++++++++++++5+++++++
++++++++++++6++++++++++++6+++++++
++++++++++++7++++++++++++7+++++++
++++++++++++8++++++++++++8+++++++
++++++++++++9++++++++++++9+++++++
+++++++++++10+++++++++++10+++++++
+++++++++++11+++++++++++11+++++++
123456789101112345678910111234567
++++++++++++1++++++++++++1+++++++
++++++++++++2++++++++++++2+++++++
++++++++++++3++++++++++++3+++++++
++++++++++++4++++++++++++4+++++++
++++++++++++5++++++++++++5+++++++
++++++++++++6++++++++++++6+++++++
++++++++++++7++++++++++++7+++++++
++++++++++++8++++++++++++8+++++++
++++++++++++9++++++++++++9+++++++

123456789101112345678910111234567

++++++++++++1++++++++++++1+++++++

++++++++++++2++++++++++++2+++++++

++++++++++++3++++++++++++3+++++++

++++++++++++4++++++++++++4+++++++

++++++++++++5++++++++++++5+++++++

++++++++++++6++++++++++++6+++++++

++++++++++++7++++++++++++7+++++++

++++++++++++8++++++++++++8+++++++

++++++++++++9++++++++++++9+++++++

+++++++++++10+++++++++++10+++++++

+++++++++++11+++++++++++11+++++++

123456789101112345678910111234567

++++++++++++1++++++++++++1+++++++

++++++++++++2++++++++++++2+++++++

++++++++++++3++++++++++++3+++++++

++++++++++++4++++++++++++4+++++++

++++++++++++5++++++++++++5+++++++

++++++++++++6++++++++++++6+++++++

++++++++++++7++++++++++++7+++++++

++++++++++++8++++++++++++8+++++++

++++++++++++9++++++++++++9+++++++

Реализация

ideone: ссылка

#include <iostream>
using namespace std;

struct point {
	
	int abscissa, ordinate;
	
	point() {
	    abscissa = 0;
	    ordinate = 0;
	}
	
	point(int x, int y) {
		abscissa = x;
		ordinate = y;
	}
	
	void setX(int x) {
	    abscissa = x;
	}
	
	void setY(int y) {
	    ordinate = y;
	}
	
	int getX() {
		return abscissa;
	}
	
	int getY() {
		return ordinate;
	}
	
};

struct size {
	
	int width, height;
	
	size() {
	    width = 0;
	    height = 0;
	}
	
	size(int w, int h) {
		width = w;
		height = h;
	}
	
	int getWidth() {
		return width;
	}
	
	int getHeight() {
		return height;
	}
	
};

struct screen {
	
	size dimension; // dimension of the screen
	point cursor; // position of the cursor
	char **arr; // array that represents characters on the screen
	
	// allocates the memory for the array and sets its dimension
	screen(size d) {
		dimension = d;
		arr = new char*[dimension.getWidth()];
		for(int i = 0; i < dimension.getWidth(); i++) {
			arr[i] = new char[dimension.getHeight()];
		}
	}
	
	// deallocates the memory for the array
	void deallocate() {
		for(int i = 0; i < dimension.getWidth(); i++) {
    		delete[] arr[i];
		}
		delete[] arr;
	}
	
	// fills each cell by character c
	void fill(char c) {
	    for(int i = 0; i < dimension.getWidth(); i++) {
	        for(int j = 0; j < dimension.getHeight(); j++) {
	            arr[i][j] = c;
	        }
	    }
	}
	
	// print integer where cursor is located and returns position of the cursor
	point print(int i) {
	    return print(to_string(i));
	}
	
	// print string where cursor is located and returns position of the cursor
	point print(string s) {
		for(int i = 0; i < s.length(); i++) {
		    arr[cursor.getX()][cursor.getY()] = s.at(i);
		    moveCursor();
		}
		return cursor;
	}
	
	// moves cursor to the right
	void moveCursor() {
		cursor.setX(cursor.getX() + 1 == dimension.getWidth() ? 0 : cursor.getX() + 1);
		cursor.setY(cursor.getX() == 0 ? cursor.getY() + 1 : cursor.getY());
	}
	
	
	// moves cursor to the point p
	void moveCursor(point p) {
		cursor.setX(p.getX());
		cursor.setY(p.getY());
	}
	
	// returns char located at point p
	char getChar(point p) {
	    return arr[p.getX()][p.getY()];
	}
	
	// returns dimension of the screen
	size getSize() {
		return dimension;
	}
	
};

// returns length of integer
int length(int number) {
    int result = 1;
    while((number /= 10) > 0) {
        result++;
    }
    return result;
}

// returns sum of lengths of integers from from to to
int length(int from, int to) {
    int result = 0;
    for(int i = from; i <= to; i++) {
        result += length(i);
    }
    return result;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    screen screen(size(length(1, k), k + 1));
    screen.fill('+');
    for(int i = 1; i <= k; i++) {
        screen.print(i);
    }
    for(int i = 1; i <= k; i++) {
    	screen.moveCursor(point(screen.getSize().getWidth() - length(i), i));
    	screen.print(i);
    }
    for(int row = 0; row < m; row++) {
        for(int col = 0; col < n; col++) {
            cout << screen.getChar(point(col % screen.getSize().getWidth(), row % screen.getSize().getHeight()));
        }
        cout << endl;
    }
    screen.deallocate();
	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

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

#include <iostream>

using namespace std;

struct point {

int abscissa, ordinate;

point() {

abscissa = 0;

ordinate = 0;

}

point(int x, int y) {

abscissa = x;

ordinate = y;

}

void setX(int x) {

abscissa = x;

}

void setY(int y) {

ordinate = y;

}

int getX() {

return abscissa;

}

int getY() {

return ordinate;

}

};

struct size {

int width, height;

size() {

width = 0;

height = 0;

}

size(int w, int h) {

width = w;

height = h;

}

int getWidth() {

return width;

}

int getHeight() {

return height;

}

};

struct screen {

size dimension; // dimension of the screen

point cursor; // position of the cursor

char **arr; // array that represents characters on the screen

// allocates the memory for the array and sets its dimension

screen(size d) {

dimension = d;

arr = new char*[dimension.getWidth()];

for(int i = 0; i < dimension.getWidth(); i++) {

arr[i] = new char[dimension.getHeight()];

}

// deallocates the memory for the array

void deallocate() {

for(int i = 0; i < dimension.getWidth(); i++) {

delete[] arr[i];

}

delete[] arr;

}

// fills each cell by character c

void fill(char c) {

for(int i = 0; i < dimension.getWidth(); i++) {

for(int j = 0; j < dimension.getHeight(); j++) {

arr[i][j] = c;

}

// print integer where cursor is located and returns position of the cursor

point print(int i) {

return print(to_string(i));

}

// print string where cursor is located and returns position of the cursor

point print(string s) {

for(int i = 0; i < s.length(); i++) {

arr[cursor.getX()][cursor.getY()] = s.at(i);

moveCursor();

}

return cursor;

}

// moves cursor to the right

void moveCursor() {

cursor.setX(cursor.getX() + 1 == dimension.getWidth() ? 0 : cursor.getX() + 1);

cursor.setY(cursor.getX() == 0 ? cursor.getY() + 1 : cursor.getY());

}

// moves cursor to the point p

void moveCursor(point p) {

cursor.setX(p.getX());

cursor.setY(p.getY());

}

// returns char located at point p

char getChar(point p) {

return arr[p.getX()][p.getY()];

}

// returns dimension of the screen

size getSize() {

return dimension;

}

};

// returns length of integer

int length(int number) {

int result = 1;

while((number /= 10) > 0) {

result++;

}

return result;

}

// returns sum of lengths of integers from from to to

int length(int from, int to) {

int result = 0;

for(int i = from; i <= to; i++) {

result += length(i);

}

return result;

}

int main() {

int n, m, k;

cin >> n >> m >> k;

screen screen(size(length(1, k), k + 1));

screen.fill('+');

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

screen.print(i);

}

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

screen.moveCursor(point(screen.getSize().getWidth() - length(i), i));

screen.print(i);

}

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

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

cout << screen.getChar(point(col % screen.getSize().getWidth(), row % screen.getSize().getHeight()));

}

cout << endl;

}

screen.deallocate();

return 0;

}

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 16

01/11/2015 by Александр Коломеец

Постановка задачи

MLoop16.

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

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

Разложим [latex]g \left( x \right) = \sin x[/latex] по формуле Тейлора с опорной точкой [latex]x_0 = 0[/latex] и остаточным членом в форме Лагранжа:
[latex]g \left( x \right) = P_n \left( x_0 ; x \right) + R_n \left( x_0 ; x \right)[/latex],
[latex]P_n \left( x_0 ; x \right) = g \left( x_0 \right) + \sum_{k = 1}^{n} \frac{g^{\left( k \right)} \left( x_0 \right) }{k!} \left( x — x_0 \right) ^k[/latex],
[latex]R_n \left( x_0 ; x \right) = \frac{g^{\left( n + 1 \right)} \left( \xi \right)}{\left( n + 1 \right) !}\left( x — x_0 \right) ^{n + 1} , x_0 < \xi < x[/latex].

Найдем производные [latex]g \left( x \right)[/latex]:
[latex]g’ \left( x \right) = \cos x = \sin \left( x + \frac{\pi}{2} \right)[/latex],
[latex]g» \left( x \right) = \cos \left( x + \frac{\pi}{2} \right) = \sin \left( x + 2 \frac{\pi}{2} \right)[/latex],
[latex]g»’ \left( x \right) = \cos \left( x + 2 \frac{\pi}{2} \right) = \sin \left( x + 3 \frac{\pi}{2} \right)[/latex],
[latex]\cdots[/latex]
[latex]g^{\left( k \right)} \left( x \right) = \cos \left( x + \left( k — 1 \right) \frac{\pi}{2} \right) = \sin \left( x + k \frac{\pi}{2} \right)[/latex].

Вычислим значение функции и ее производных в точке [latex]x_0[/latex]:
[latex]g \left( x_0 \right) = \sin x_0 = \sin 0 = 0[/latex],
[latex]g’ \left( x_0 \right) = \sin \left( x_0 + \frac{\pi}{2} \right) = \sin \frac{\pi}{2} = 1[/latex],
[latex]g» \left( x_0 \right) = \sin \left( x_0 + 2 \frac{\pi}{2} \right) = \sin \pi = 0[/latex],
[latex]g»’ \left( x_0 \right) = \sin \left( x_0 + 3 \frac{\pi}{2} \right) = \sin \frac{3 \pi}{2} = -1[/latex],
[latex]\cdots[/latex]
[latex]g ^{ \left( 2k — 1 \right) } \left( x_0 \right) = \sin \left( x_0 + \left( 2k — 1 \right) \frac{\pi}{2} \right) = \sin \left( \pi k + \frac{\pi}{2} \right) = \left( -1 \right) ^{k — 1}[/latex],
[latex]g ^{ \left( 2k \right) } \left( x_0 \right) = \sin \left( x_0 + 2k \frac{\pi}{2} \right) = \sin \pi k = 0[/latex].

Тогда
[latex]P_n \left( x_0 ; x \right) = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot x^{2k — 1} }{ \left( 2k — 1 \right) ! }[/latex],
[latex]R_n \left( x_0 ; x \right) = \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot x ^{n + 1} }{ \left( n + 1 \right) ! }[/latex],
[latex]g \left( x \right) = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot x^{2k — 1} }{ \left( 2k — 1 \right) ! } + \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot x ^{n + 1} }{ \left( n + 1 \right) ! }[/latex],
[latex]f \left( x \right) = \frac{ g \left( 2x \right) }{ x } = \sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! } + \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot \left( 2x \right) ^{n + 1} }{ x \cdot \left( n + 1 \right) ! }[/latex].

Осталось найти такое [latex]n \in \mathbb{N}[/latex], чтобы выполнялось неравенство
[latex]\left| \frac{\sin \left( \xi + \left( n + 1 \right) \frac{\pi}{2} \right) \cdot \left( 2x \right) ^{n + 1} }{ x \cdot \left( n + 1 \right) ! } \right| \le \left| \frac{ \left( 2x \right) ^ {n + 1} }{ x \left( n + 1 \right) ! } \right| < \epsilon[/latex].

Для ускорения вычислений зададим реккурентную формулу для слагаемых суммы
[latex]\sum_{k = 1}^{ \lceil \frac{n}{2} \rceil } \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! }[/latex].
Представим каждое слагаемое суммы в виде
[latex]\alpha_k = \alpha_{k — 1} \cdot b_k = \frac{ \left( -1 \right) ^{k — 1} \cdot \left( 2x \right) ^{2k — 1} }{ x \cdot \left( 2k — 1 \right) ! }[/latex].
Выразим [latex]b_k[/latex]:
[latex]b_k = \frac{ \alpha_k }{ \alpha_{ k — 1 } } = \frac{ \left( -1 \right) ^ {k — 1} \cdot \left( 2x \right) ^ {2k — 1} \cdot x \left( 2 \left( k — 1 \right) — 1 \right) ! }{ x \left( 2k — 1 \right) ! \cdot \left( -1 \right) ^ { \left( k — 1 \right) — 1 } \cdot \left( 2x \right) ^ {2 \left( k — 1 \right) — 1} } = — \frac{4x^2}{\left( 2k — 2 \right) \left( 2k — 1 \right)}[/latex].
Тогда
[latex]\alpha_k = \begin{cases} 2 & k = 1, \\ \alpha_{k-1} \cdot b_k & k > 1. \end{cases}[/latex]

Тесты

Входные данные		Выходные данные
[latex]x[/latex]	[latex]\epsilon[/latex]	[latex]f\left( x \right) = \frac{\sin 2x}{x} + \lambda, \lambda\in\left( -\epsilon;\epsilon \right)[/latex]
[latex]\frac{5\pi}{2}[/latex]	[latex]0[/latex]	[latex]\frac{2}{5\pi}[/latex]
[latex]\pi[/latex]	[latex]0.01[/latex]	[latex]0[/latex]
[latex]0[/latex]	[latex]0.1[/latex]	[latex]\emptyset[/latex]

Реализация

ideone: ссылка

#include <iostream>
using namespace std;

double abs(double argument) {
	return argument >= 0 ? argument : -argument;
}

int ceil(double argument) {
	int result = (int) argument;
	if((double) result != argument && argument > 0) {
		result++;
	} else if((double) result == argument && argument < 0) {
		result++;
	}
	return result;
}

int determineOrderOfPolynomial(double argument, double accuracy) {
	int order = 1;
	double a = 2 * argument;
	while(abs(a) >= accuracy) {
		order++;
		a *= 2 * argument / (order + 1);
	}
	return order;
}

double function(double argument, double accuracy) {
	int order = determineOrderOfPolynomial(argument, accuracy);
	double summand = 2;
	double sum = summand;
	for(int k = 2; k <= ceil(order / 2.0); k++) {
		summand *= -4 * argument * argument / ((2 * k - 2) * (2 * k - 1));
		sum += summand;
	}
	return sum;
}

int main() {
	double argument, accuracy;
	cin >> argument >> accuracy;
	if(argument == 0) {
		cout << "empty set";
	} else {
		cout << function(argument, accuracy);
	}
	cout << endl;
	return 0;
}

#include <iostream>

using namespace std;

double abs(double argument) {

return argument >= 0 ? argument : -argument;

}

int ceil(double argument) {

int result = (int) argument;

if((double) result != argument && argument > 0) {

result++;

} else if((double) result == argument && argument < 0) {

result++;

}

return result;

}

int determineOrderOfPolynomial(double argument, double accuracy) {

int order = 1;

double a = 2 * argument;

while(abs(a) >= accuracy) {

order++;

a *= 2 * argument / (order + 1);

}

return order;

}

double function(double argument, double accuracy) {

int order = determineOrderOfPolynomial(argument, accuracy);

double summand = 2;

double sum = summand;

for(int k = 2; k <= ceil(order / 2.0); k++) {

summand *= -4 * argument * argument / ((2 * k - 2) * (2 * k - 1));

sum += summand;

}

return sum;

}

int main() {

double argument, accuracy;

cin >> argument >> accuracy;

if(argument == 0) {

cout << "empty set";

} else {

cout << function(argument, accuracy);

}

cout << endl;

return 0;

}

Related Images:

MLoops 23

01/11/2015 by Сплошнов Кирилл

Условие

0, 1, 8, 27, 64, 125, 216
, 343, 512, 729, 1000, 13
31, 1728, 2197, 2744, 337
5, 4096, 4913, 5832, 6859
, 8000, 9261, 10648, 1216
7, 13824, 15625, 17576, 1
9683, 21952, 24389, 27000
, 29791, 32768, 35937, 39

0, 1, 8, 27, 64, 125, 216

, 343, 512, 729, 1000, 13

31, 1728, 2197, 2744, 337

5, 4096, 4913, 5832, 6859

, 8000, 9261, 10648, 1216

7, 13824, 15625, 17576, 1

9683, 21952, 24389, 27000

, 29791, 32768, 35937, 39

Тесты

[latex]n \times {m}[/latex]	Выходные данные
[latex]2 \times {2}[/latex]	0, _1
[latex]2 \times {10}[/latex]	0, _1 , 8, _2 7, _6 4, _1 25
[latex]5 \times {5}[/latex]	0, 1, _8, 2 7, 64 , 125 , 216
[latex]20 \times {1}[/latex]	0, 1, 8, 27, 64, 125
[latex]22 \times {10}[/latex]	0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 10 00, 1331, 1728, 2197, 2744, 3375, 4096, 4913 , 5832, 6859, 8000, 92 61, 10648, 12167, 1382 4, 15625, 17576, 19683 , 21952, 24389, 27000, _29791, 32768, 35937, 39304, 42875, 46656, 5

(Нижние подчеркивания в таблице добавил намеренно, там, где строка начинается с пробела, так как они автоматически убирались.)

Решение

Нетрудно заметить, что данная последовательность содержит кубы натуральных чисел, разделенные запятой с пробелом (единственное отличие, первое число — ноль). Очевидно, понадобится использовать 2 цикла, внешний (для строк) и внутренний (для столбцов). Для простоты я попробовал составить алгоритм так, чтобы:

а) во внешнем цикле не было ничего, кроме перехода на новую строку;

б) за один шаг внутреннего цикла печатался ровно 1 символ.

Проанализируем ключевые моменты. Во первых, числа надо будет выводить по одной цифре за раз. Так как мы не знаем длину числа, можно воспользоваться функцией [latex]log10[/latex], но намного проще выводить число в обратном порядке (используя деление по модулю 10), поэтому при вычислении очередного куба будем сохранять его во временную переменную, а в печатаемую переменную [latex]cube[/latex] будем сохранять это число, записанное в обратном порядке, и выводить его на экран также в обратном порядке (таким образом, получая исходный порядок).

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

Единственный недочет — числа вроде 1000, так как при инверсии получим 0001, то есть число 1. Я решил эту проблему, заведя переменную [latex]zeros[/latex], хранящую кол-во таких нулей. Начальное число ноль тоже учтено в коде (см. комментарии).

Код

#include <iostream>
using namespace std;

int main() 
{
	int n, m;
	cin >> n >> m;
	long num = 0, cube = 0;
	bool addSpacebar = false;
	int zeros = 0;
	for (int i = 0; i < m; i ++)
	{
		for (int j = 0; j < n; j ++)
		{
			if (addSpacebar) //если необходим пробел
			{
				cout << " ";
				addSpacebar = false;
			}
			else if (cube > 0 || num + j == 0) //печатаем текущую цифру пока число больше нуля, num + j == 0 позволяют напечатать число 0
			{
				cout << cube % 10;
				cube /= 10;
			}
			else if (zeros > 0) //если закончили печатать число, но у него остались "потерянные" нули, выводим их пока не закончатся
			{
				cout << 0;
				zeros --;
			}
			else //иначе
			{
				cout << ","; //печатаем запятую
				addSpacebar = true; //запоминаем, что нужен пробел
				num ++;
				long L = num * num * num; //получаем куб следующего числа
				while (L > 0) //записываем его в обратного порядке
				{
					cube *= 10;
					cube += L % 10;
					if (cube == 0) 
						zeros ++; //если число L заканчивалось на ноль, запоминаем его (ноль)
					L /= 10;
				}
			}
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, m;

cin >> n >> m;

long num = 0, cube = 0;

bool addSpacebar = false;

int zeros = 0;

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

{

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

{

if (addSpacebar) //если необходим пробел

{

cout << " ";

addSpacebar = false;

}

else if (cube > 0 || num + j == 0) //печатаем текущую цифру пока число больше нуля, num + j == 0 позволяют напечатать число 0

{

cout << cube % 10;

cube /= 10;

}

else if (zeros > 0) //если закончили печатать число, но у него остались "потерянные" нули, выводим их пока не закончатся

{

cout << 0;

zeros --;

}

else //иначе

{

cout << ","; //печатаем запятую

addSpacebar = true; //запоминаем, что нужен пробел

num ++;

long L = num * num * num; //получаем куб следующего числа

while (L > 0) //записываем его в обратного порядке

{

cube *= 10;

cube += L % 10;

if (cube == 0)

zeros ++; //если число L заканчивалось на ноль, запоминаем его (ноль)

L /= 10;

}

cout << endl;

}

return 0;

}

Ссылки

Рабочий код на Ideaone.

Тут можно посмотреть саму последовательность.

Related Images:

MLoop 20

01/11/2015 by Кудымовская Вика

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

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

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

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

Вывести значение суммы ряда.

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

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

№	Входные данные	Выходные данные
1.	0.1	0.666667
2.	0.01	0.736626
3.	0.001	0.749276
4.	0.0001	0.749903
5.	0.0000001	0.75

Реализация (первый вариант кода)

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

int main() {
	int i;
	double E; // переменная для обозначения точности
	double a = 1/3.0, sum = 1/3.0;
  	//присваиваем переменным a(член ряда) и sum значение первого члена ряда
 	cin >> E;
 	/*a *= (i+1)/(3*i) - формула для вычисления очередного члена ряда*/
 	for (i = 1; fabs(a *= (double)(i+1)/(3*i)) >= E; i++)
 	{
    	sum +=a;
 	}
 	cout << sum << endl;
 	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int i;

double E; // переменная для обозначения точности

double a = 1/3.0, sum = 1/3.0;

//присваиваем переменным a(член ряда) и sum значение первого члена ряда

cin >> E;

/*a *= (i+1)/(3*i) - формула для вычисления очередного члена ряда*/

for (i = 1; fabs(a *= (double)(i+1)/(3*i)) >= E; i++)

{

sum +=a;

}

cout << sum << endl;

return 0;

}

Реализация (второй вариант кода)

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

double arr(double sum, double a, double E, int i)
{
	if (fabs(a *= (double)(i + 1) * pow(3 * i, -1)) < E)
	{
		return sum;
	}
	else
	{
		i++;
		sum += a;
		return arr(sum, a, E, i);
	}
}
int main()
{
	int i=1;
	double E; // переменная для обозначения точности
	double a = 1 / 3.0, sum = 1 / 3.0;
	//присваиваем переменным a(член ряда) и sum значение первого члена ряда
	cin >> E;
	cout << arr(sum, a, E, i) << endl;
	system("pause");
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double arr(double sum, double a, double E, int i)

{

if (fabs(a *= (double)(i + 1) * pow(3 * i, -1)) < E)

{

return sum;

}

else

{

i++;

sum += a;

return arr(sum, a, E, i);

}

int main()

{

int i=1;

double E; // переменная для обозначения точности

double a = 1 / 3.0, sum = 1 / 3.0;

//присваиваем переменным a(член ряда) и sum значение первого члена ряда

cin >> E;

cout << arr(sum, a, E, i) << endl;

system("pause");

return 0;

}

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

Выводим формулу для вычисления значения каждого последующего члена ряда: [latex]a_{n+1}=a_n\cdot \frac{i+1}{3^{i+1}}\cdot \frac{3^i}{i}=a_n\cdot \frac{i+1}{3i}[/latex].
Вычисляем значение первого члена ряда: [latex]a[/latex]: [latex]a=\frac{i}{3^i}=\frac{1}{3}[/latex].
Присваиваем [latex]sum[/latex] значение первого члена ряда.
Абсолютное значение каждого последующего члена ряда сравниваем с [latex]\varepsilon[/latex]: при условии, что [latex]|a_{n+1}|\geq\varepsilon[/latex], накапливается сумма (значение суммы увеличивается на очередной член ряда [latex]a_{n+1}[/latex]). Если же [latex]|a_{n+1}|<\varepsilon[/latex], выводится значение суммы ряда.

Для запроса на выполнение следует перейти по ссылке (первый вариант кода).

Для запроса на выполнение следует перейти по ссылке (второй вариант кода).

Related Images:

MLoops24

01/11/2015 by Таран Таня

0 10 1110 3110 132110 1113122110
311311222110 13211321322110 1113
122113121113222110 3113112221131
1123113322110 132113213221133112
132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110

311311222110 13211321322110 1113

122113121113222110 3113112221131

1123113322110 132113213221133112

132123223110 1113122113121113222

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

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

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

Построенная для данной последовательности таблица с соответствующим количеством столбцов и строк.

Тесты

[latex]n[/latex]

[latex]m[/latex]

Результат работы программы

0
10

0 10

1110

3110

1321

0 10

1110

3110

13211

0 111

0 10 1110 3110 132110 1113122110
311311222110 13211321322110 1113
122113121113222110 3113112221131
1123113322110 132113213221133112
132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110

311311222110 13211321322110 1113

122113121113222110 3113112221131

1123113322110 132113213221133112

132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110 311311222110 1321
1321322110 1113122113121113222110 3113112221131112
3113322110 132113213221133112132123222110 11131221
131211132221232112111312111213322110 3113112221131
1123113321112131221123113111231121123222110 132113
21322113311213212312311211131122211213211331121321
12211213322110 11131221131211132221232112111312111
21311121321123113213221121113122123211211131221222
1121123222110 311311222113111231133211121312211231
13111231121113311211131221121321131211132221123113

0 10 1110 3110 132110 1113122110 311311222110 1321

1321322110 1113122113121113222110 3113112221131112

3113322110 132113213221133112132123222110 11131221

131211132221232112111312111213322110 3113112221131

1123113321112131221123113111231121123222110 132113

21322113311213212312311211131122211213211331121321

12211213322110 11131221131211132221232112111312111

21311121321123113213221121113122123211211131221222

1121123222110 311311222113111231133211121312211231

13111231121113311211131221121321131211132221123113

0 10 1110

3110 13211

0 11131221

10 3113112

22110 1321

1321322110

1113122113

1211132221

Алгоритм

Для начала определим алгоритм построения предоставленной последовательности. Перед нами так называемая Look-and-Say sequence, начинающаяся с 0. Чтобы получить последующий член последовательности, нам потребуется обратиться к предыдущему и выполнить следующее:

Посчитать количество одинаковых подряд идущих цифр и записать его.
Записать саму эту цифру.

Разберем на примере:

Первый член последовательности — [latex]0[/latex] («Основание» последовательности);
Второй член последовательности — [latex]10[/latex] («Вижу» один ноль);
Третий член последовательности — [latex]1110[/latex] («Вижу» одну единицу и один ноль);
Четвертый член последовательности — [latex]3110[/latex] («Вижу» три единицы и один ноль).
…

Реализуем данное построение на практике. Создадим два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (изначально start [latex] = 0[/latex]) и счетчик количества совпадающих элементов (изначально quantity [latex] = 0[/latex]). Запустим цикл от первого до последнего элемента массива previousTerm и выполним ряд действий, а именно:

Пока последующие элементы совпадают с текущим сравниваемым, инкрементируем счетчик.
Как только находиться элемент не совпадающий с текущим сравниваемым, выполняем вывод количества вхождений и само число, также записываем данные значения в вектор currentTerm. Переходим к следующей цифре для сравнения и присваиваем счетчику значение [latex]1[/latex].
Отдельно выполняем предыдущий пункт для последней последовательности цифр или одной цифры, так как нет возможности сравнения с последующими.
Как только один член последовательности полностью построен, обнуляем значения индекса сравниваемой цифры и счетчика. Также очищаем вектотр previousTerm и передаем ему значения вектора currentTerm, очищаем вектор currentTerm.

Теперь наша задача состоит в том, чтобы выполнить правильный вывод таблицы. Основную работу по построению таблицы будет выполнять метод ToPrint, принимающий как параметры заданное количество столбцов, строк, номер текущего столбца, текущей строки и цифру которую нужно вывести на печать (или пробел).
Рассмотрим детали его работы:

При запуске метода сразу же увеличиваем текущий номер столбца, в который записывается символ, на [latex]1[/latex].
Далее проверяем не превышает ли номер текущего столбца возможный. Если это так, то выполняем перевод курсора на новую строку, присваиваем текущему столбцу значение [latex]1[/latex] и инкрементируем значение номера текущей строки.
Если количество строк превышает заданное, заканчиваем работу программы.
В противном же случае выполняем печать символа, если это не пробел в начале строки (если это все же пробел в начале строки, то ничего не печатаем и уменьшаем значение текущего столбца для печати). Для упрощения вывода пробел передается в метод по его коду в таблице ASCII — [latex]32[/latex]. Мы имеем полное право использовать число [latex]32[/latex] без угрозы ошибки, так как передавать мы будем только цифры [latex]0, 1, 2, 3[/latex].

Таким образом общий алгоритм работы программы можем сформулировать так:

Считываем заданное количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]).
Для последующей работы объявляем переменные хранящие значения номера текущего столбца и строки (currentNumberColumn и currentNumberRow соответственно), два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (start) и счетчик количества совпадающих элементов (quantity) .
Отправляем в вектор previousTerm значение «основания» последовательности — [latex]0[/latex].
Выводим первый член последовательности и пробел после него (если потребуется).
Далее запускаем бесконечный цикл, так как окончание работы программы предусмотрено в методе ToPrint.
И выполняем последовательное построение членов последовательности (описано выше) и тут же вывод, пока количество строк не превышает заданное.

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

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

void ToPrint(int n, int m, int *currentNumberColumn, int *currentNumberRow, int symbolToPrint) {
	(*currentNumberColumn)++; // Инкрементируем значение номера столбца, так как есть символ на печать
	if (*currentNumberColumn > n) {
		cout << endl; // Переходим на новую строку
	  	(*currentNumberRow)++;
	  	*currentNumberColumn = 1; 
	} // Если следует выполнить переход на следующую строку, выполняем этот переход по всем индексам
	if (*currentNumberRow > m)
	    exit(0); // Заканчиваем работу программы, как только количество строк превышает заданное
	else if (symbolToPrint == 32 && *currentNumberColumn == 1) // В таблице ASCII 32 - пробел
	    (*currentNumberColumn)--; // Возвращаем предыдущее значение номера столбца, так как ничего не было напечатано
    else if (symbolToPrint == 32)
        cout << char(symbolToPrint); // Выводим пробел, если это не начало строки
    else
      	cout << symbolToPrint;
}

int main() {
	int n, m; // Количество столбцов и строк соответственно
	cin >> n >> m;
	int start = 0; // Индекс элемента текущей цифры с которой ведется сравнение
    int quantity = 0; // Количество идущих подряд одинаковых элементов в данном члене
    int currentNumberRow = 1; // Номер текущей строки, в которой будет записан символ
    int currentNumberColumn = 0; // Номер текущего столбца, в который будет записан символ
    vector <short> currentTerm; // Вектор, хранящий значение текущего члена последовательности
    vector <short> previousTerm; // Вектор, хранящий значение предыдущего члена последовательности
	previousTerm.push_back(0); // Записываем в вектор предыдущего члена значение первого члена последовательности
    ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 0); // Выводим первый член последовательности
    ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Выводим пробел после него (если он не понадобится его уберет метод ToPrint)
    while (true) {
           for (int i = 0; i < previousTerm.size(); i++) { 
    	        if (previousTerm[i] == previousTerm[start]) 
    	 	        quantity++; // Считаем количество идущих подряд одинаковых цифр
    	        else {
    		      	currentTerm.push_back(quantity); // Записываем в вектор количество текущих цифр
    	          	currentTerm.push_back(previousTerm[start]); // Записываем саму цифру
    	          	ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);
    	          	ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]); // Печатаем полученные данные
    	          	start += quantity; // Переходим к следующей цифре для сравнения
    	          	quantity = 1; // Присваиваем количеству одинаковых идущих подряд цифр 1, так как мы перешли к следующей цифре
    	        } // Если значение текущей цифры не совпадает с предыдущим, выполняем вывод и заполнение вектора следующего члена
    	        if (i == (previousTerm.size() - 1)) {
    	            currentTerm.push_back(quantity); 
    	            currentTerm.push_back(previousTerm[start]);
    	            ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);
    	            ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]);
    	        } // Отдельный вывод для последнего элемента данного члена
           } // Цикл для прохода по всем цифрам предыдущего члена последовательности
           start = 0;      
           quantity = 0; // Обнуляем все параметры для подсчета, так как дальше будем работать со следующим членом последовательности
           ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Печатаем пробел после текущего члена последовательности
           previousTerm.clear(); 
           previousTerm = currentTerm; // Записываем в вектор предыдущего члена текущий построенный член последовательности
           currentTerm.clear();
    } // Бесконечный цикл, так как условие окончание работы программы задано в методе печати
}

#include <iostream>

#include <vector>

using namespace std;

void ToPrint(int n, int m, int *currentNumberColumn, int *currentNumberRow, int symbolToPrint) {

(*currentNumberColumn)++; // Инкрементируем значение номера столбца, так как есть символ на печать

if (*currentNumberColumn > n) {

cout << endl; // Переходим на новую строку

(*currentNumberRow)++;

*currentNumberColumn = 1;

} // Если следует выполнить переход на следующую строку, выполняем этот переход по всем индексам

if (*currentNumberRow > m)

exit(0); // Заканчиваем работу программы, как только количество строк превышает заданное

else if (symbolToPrint == 32 && *currentNumberColumn == 1) // В таблице ASCII 32 - пробел

(*currentNumberColumn)--; // Возвращаем предыдущее значение номера столбца, так как ничего не было напечатано

else if (symbolToPrint == 32)

cout << char(symbolToPrint); // Выводим пробел, если это не начало строки

else

cout << symbolToPrint;

}

int main() {

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

cin >> n >> m;

int start = 0; // Индекс элемента текущей цифры с которой ведется сравнение

int quantity = 0; // Количество идущих подряд одинаковых элементов в данном члене

int currentNumberRow = 1; // Номер текущей строки, в которой будет записан символ

int currentNumberColumn = 0; // Номер текущего столбца, в который будет записан символ

vector <short> currentTerm; // Вектор, хранящий значение текущего члена последовательности

vector <short> previousTerm; // Вектор, хранящий значение предыдущего члена последовательности

previousTerm.push_back(0); // Записываем в вектор предыдущего члена значение первого члена последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 0); // Выводим первый член последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Выводим пробел после него (если он не понадобится его уберет метод ToPrint)

while (true) {

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

if (previousTerm[i] == previousTerm[start])

quantity++; // Считаем количество идущих подряд одинаковых цифр

else {

currentTerm.push_back(quantity); // Записываем в вектор количество текущих цифр

currentTerm.push_back(previousTerm[start]); // Записываем саму цифру

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]); // Печатаем полученные данные

start += quantity; // Переходим к следующей цифре для сравнения

quantity = 1; // Присваиваем количеству одинаковых идущих подряд цифр 1, так как мы перешли к следующей цифре

} // Если значение текущей цифры не совпадает с предыдущим, выполняем вывод и заполнение вектора следующего члена

if (i == (previousTerm.size() - 1)) {

currentTerm.push_back(quantity);

currentTerm.push_back(previousTerm[start]);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]);

} // Отдельный вывод для последнего элемента данного члена

} // Цикл для прохода по всем цифрам предыдущего члена последовательности

start = 0;

quantity = 0; // Обнуляем все параметры для подсчета, так как дальше будем работать со следующим членом последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Печатаем пробел после текущего члена последовательности

previousTerm.clear();

previousTerm = currentTerm; // Записываем в вектор предыдущего члена текущий построенный член последовательности

currentTerm.clear();

} // Бесконечный цикл, так как условие окончание работы программы задано в методе печати

}

Ссылки

Код программы
Дополнительная информация о «Look-and-Say» sequence:
Источник 1; Источник 2; Источник 3; Источник 4;

Related Images:

MLoop22

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

Условие

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

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

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

Код

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

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

#include <iostream>

#include <cmath>

using namespace std;

int main() {

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

cin >> E;

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

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

cout << sum;

return 0;

}

Решение

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

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

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

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

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

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

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

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

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

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

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

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

cout << sum;

1	cout << sum;

Ссылки

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

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

Related Images:

MLoops22

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

Условие

1491625364964811001211441
6919622525628932436140044
1484529576625676729784841
9009611024108911561225129

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

№	Входные данные	Выходные данные
1	1 1	1
2	7 1	1491625
3	10 2	1491625364 9648110012
4	1 3	1 4 9
5	1 6	1 4 9 1 6 2
6	5 5	14916 25364 96481 10012 11441
7	25 4	1491625364964811001211441 6919622525628932436140044 1484529576625676729784841 9009611024108911561225129

Код

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

// Возвращает длину числа
int GetLength(int a) {
	return (a==0?1:log10(a)+1);
}

// Возвращает левую часть числа до заданной цифры включительно
int LeftPart(int a, int n) {
	return a/pow(10, GetLength(a) - n);
}

// Возвращает правую часть числа после заданной цифры
int RightPart(int a, int n) {
	int p = pow(10, GetLength(a) - n);
	return a%p;
}

int main() {
	int n, m, i = 0, toPrint; // Столбцы, строки, счетчик очередного числа для возведения в квадрат, текущее значение для печати
	bool haveRest = false;	// Есть ли часть числа, "отрезанная" после переноса строки
	cin >> n >> m;
	int columnsLeft = n;	// Присваиваем переменной для оставшихся свободных столбцов значения общего количества столбцов
	while(m > 0) {
		if(columnsLeft == 0) {	// Если не осталось свободных столбцов
			m--;
			if(m > 0)
				cout << endl;
			columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
			haveRest = false;	// "Отрезанной" части числа нет
		} else {	// Если есть свободные столбцы
			i = (haveRest?i:++i);
			toPrint = (haveRest?toPrint:i*i);	// Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа
			if(GetLength(toPrint) <= columnsLeft) {	// Если хватает свободных столбцов для печати числа в toPrint
				cout << toPrint;
				columnsLeft -= GetLength(toPrint);	// Обновляем количество свободных столбцов
				haveRest = false;	// "Отрезанной" части числа нет
			} else {	// Если свободных столбцов не хватает для печати числа в toPrint целиком
				cout << LeftPart(toPrint, columnsLeft);	// Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы
				toPrint = RightPart(toPrint, columnsLeft);	// Присваиваем toPrint значение его ненапечатанной части
				m--;
				if(m > 0)
					cout << endl;
				columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
				haveRest = true;	// "Отрезанная" часть числа есть
			}
		}
	}
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

// Возвращает длину числа

int GetLength(int a) {

return (a==0?1:log10(a)+1);

}

// Возвращает левую часть числа до заданной цифры включительно

int LeftPart(int a, int n) {

return a/pow(10, GetLength(a) - n);

}

// Возвращает правую часть числа после заданной цифры

int RightPart(int a, int n) {

int p = pow(10, GetLength(a) - n);

return a%p;

}

int main() {

int n, m, i = 0, toPrint; // Столбцы, строки, счетчик очередного числа для возведения в квадрат, текущее значение для печати

bool haveRest = false; // Есть ли часть числа, "отрезанная" после переноса строки

cin >> n >> m;

int columnsLeft = n; // Присваиваем переменной для оставшихся свободных столбцов значения общего количества столбцов

while(m > 0) {

if(columnsLeft == 0) { // Если не осталось свободных столбцов

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = false; // "Отрезанной" части числа нет

} else { // Если есть свободные столбцы

i = (haveRest?i:++i);

toPrint = (haveRest?toPrint:i*i); // Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

if(GetLength(toPrint) <= columnsLeft) { // Если хватает свободных столбцов для печати числа в toPrint

cout << toPrint;

columnsLeft -= GetLength(toPrint); // Обновляем количество свободных столбцов

haveRest = false; // "Отрезанной" части числа нет

} else { // Если свободных столбцов не хватает для печати числа в toPrint целиком

cout << LeftPart(toPrint, columnsLeft); // Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы

toPrint = RightPart(toPrint, columnsLeft); // Присваиваем toPrint значение его ненапечатанной части

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = true; // "Отрезанная" часть числа есть

}

return 0;

}

Решение

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

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

Опираясь на вышеперечисленное, опишем алгоритм работы цикла построения таблицы более подробно:

В первую очередь проверяется условие продолжения цикла. Цикл будет выполняться до тех пор, пока количество полностью напечатанных строк (то есть строк, длина которых равна заданному количеству столбцов) будет меньше требуемого количества строк в готовой таблице.
Определяется количество свободных столбцов в текущей строке. Если оно равно нулю, выполняется перевод на новую строку, количество полностью напечатанных строк увеличивается на [latex]1[/latex] и итерация цикла завершается.
Определяется последовательность цифр, печатаемая в текущей итерации цикла. Если с прошлой итерации в результате переноса строки осталась «отрезанная» часть числа, то в этой итерации будет выводиться она; иначе же будет выводиться квадрат очередного натурального числа.
Проверяется, сможет ли число, сформированное на предыдущем шаге, полностью уместиться в текущей строке. Если его длина меньше или равна количеству свободных столбцов, то оно выводится в поток и итерация цикла завершается; в противном случае выводится та его часть, которая может уместиться в строке, ненапечатанная часть сохраняется и будет выведена в следующей итерации (если выполнится условие продолжения цикла), количество полностью напечатанных строк увеличивается на [latex]1[/latex] и итерация цикла также завершается.

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

int i для хранения очередного натурального числа, квадрат которого нужно вычислить;
int toPrint для хранения числа, которое нужно будет выводить в очередной итерации цикла;
int columnsLeft для хранения числа свободных столбцов в текущей строке;
bool haveRest для обозначения наличия или отсутствия «отрезанной» в результате переноса строки части числа;
функция int GetLength(int a), возвращающая длину числа a;
функция int LeftPart(int a, int n), возвращающая левую часть числа a до n-той цифры включительно;
функция int RightPart(int a, int n), возвращающая правую часть числа a после n-той цифры.

До начала выполнения цикла присвоим переменной haveRest значение false («отрезанные» части чисел могут появится не раньше второй итерации), а переменной columnsLeft — считанное значение количества столбцов в таблице n.

Составим код цикла, следуя описанному выше алгоритму построения таблицы. Условием продолжения цикла будет наличие не напечатанных до конца строк m (в дальнейшем будем декрементировать m всякий раз при переносе строки):

while(m > 0)

1	while(m > 0)

Теперь выполняем проверку на наличие свободных столбцов в текущей строке. Если окажется, что в строке свободных столбцов не осталось, выполняем перенос на новую строку, после чего восстанавливаем число оставшихся столбцов (задаем переменной columnsLeft значение количества столбцов в таблице n) и указываем, что «отрезанная» часть отсутствует:

if(columnsLeft == 0) {	// Если не осталось свободных столбцов
	m--;
	if(m > 0)
		cout << endl;
	columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
	haveRest = false;	// "Отрезанной" части числа нет
}

if(columnsLeft == 0) { // Если не осталось свободных столбцов

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = false; // "Отрезанной" части числа нет

}

Если же свободные столбцы есть, определяем число, которое будет печататься в этой итерации. В случае, если «отрезанная» часть отсутствует, переменной toPrint присваиваем значение квадрата очередного натурального числа, иначе оставляем ее без изменений ( toPrint получает значение ненапечатанной части числа в конце цикла, если таковая имеется):

i = (haveRest?i:++i);
toPrint = (haveRest?toPrint:i*i);	// Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

1 2	i = (haveRest?i:++i); toPrint = (haveRest?toPrint:i*i); // Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

Наконец, оценим, может ли число, хранящееся в toPrint, уместиться в текущей строке. Если может, то выводим его, обновляем число свободных столбцов в строке и указываем, что «отрезанной» части числа нет:

if(GetLength(toPrint) <= columnsLeft) {	// Если хватает свободных столбцов для печати числа в toPrint
	cout << toPrint;
	columnsLeft -= GetLength(toPrint);	// Обновляем количество свободных столбцов
	haveRest = false;	// "Отрезанной" части числа нет
}

if(GetLength(toPrint) <= columnsLeft) { // Если хватает свободных столбцов для печати числа в toPrint

cout << toPrint;

columnsLeft -= GetLength(toPrint); // Обновляем количество свободных столбцов

haveRest = false; // "Отрезанной" части числа нет

}

В противном случае печатаем ту часть числа, которая помещается в строке, после чего присваиваем переменной toPrint значение ненапечатанной части, выполняем перенос строки, восстанавливаем количество свободных столбцов и указываем, что имеется «отрезанная» часть числа. Таким образом, в следующей итерации (если выполнится условие продолжения цикла) выводиться будет не очередной квадрат, а правая часть числа, которая не уместилась в предыдущей строке.

else {	// Если свободных столбцов не хватает для печати числа в toPrint целиком
	cout << LeftPart(toPrint, columnsLeft);	// Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы
	toPrint = RightPart(toPrint, columnsLeft);	// Присваиваем toPrint значение его ненапечатанной части
	m--;
	if(m > 0)
		cout << endl;
	columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
	haveRest = true;	// "Отрезанная" часть числа есть
}

else { // Если свободных столбцов не хватает для печати числа в toPrint целиком

cout << LeftPart(toPrint, columnsLeft); // Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы

toPrint = RightPart(toPrint, columnsLeft); // Присваиваем toPrint значение его ненапечатанной части

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = true; // "Отрезанная" часть числа есть

}

Ссылки

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

Последовательность в OEIS;

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

Related Images:

MLoop 23

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

Задача:

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

Входные данные: Точность [latex]\varepsilon[/latex].

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

Тесты:

0.1

0.01

0.001

0.0001

№	Точность [latex]\varepsilon[/latex]	Сумма ряда [latex]{\sum_{i=1}^\infty}\frac{(-1)^i}{i!}[/latex]
1	0.1	0.375
2	0.01	0.366667
3	0.001	0.367857
4	0.0001	0.367882

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

int main() {
   double E; // Точность
   cin >> E;
   double x = 1;// ((-1)^0)/0! = 1 : первое слагаемое
   double sum = 1;// При любой точности сумма начинается с первого члена
   for(int i = 1; abs(x) > E; i++){ // Цикл подсчета суммы пока слагаемое больше точности
      x = -x/i; // С каждым действием знак меняется на противоположный
      sum += x;
   }
   cout << sum;
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double E; // Точность

cin >> E;

double x = 1;// ((-1)^0)/0! = 1 : первое слагаемое

double sum = 1;// При любой точности сумма начинается с первого члена

for(int i = 1; abs(x) > E; i++){ // Цикл подсчета суммы пока слагаемое больше точности

x = -x/i; // С каждым действием знак меняется на противоположный

sum += x;

}

cout << sum;

return 0;

}

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

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

Для начала, программа читает входные данные и присваивает их переменной [latex]\varepsilon[/latex](точность). Также вводим переменную [latex]sum[/latex], равную первому члену (на случай если введенная точность не позволит циклу начаться), накапливающую сумму ряда.

Далее следует цикл [latex]for[/latex] считающий сумму членов [latex]x[/latex] пока не достигнет точности [latex]\varepsilon[/latex]. Цикл прибавляет к [latex]sum[/latex] слагаемое, деленное на [latex]i[/latex] и с противоположным знаком. По окончании цикла выводим значение суммы [latex]sum[/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:

MLoop 24

31/10/2015 by Настя Филипчук

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

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

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

В условии нужно найти сумму ряда,задан его общий член. Благодаря этому можно найти формулу, согласно которой каждый последующий член ряда выражается как предыдущий, умноженный на выражение: [latex]\frac{-2}{2 \cdot k + 3}[/latex].
Вычисляется первый член ряда, предполагается, что он и будет равен сумме ряда, и этот член ряда сравнивается по модулю с заданной точностью [latex]\varepsilon [/latex].
В случае, если требуемая точность не достигнута — подсчитывается следующий член ряда, он прибавляется к сумме и сравнивается по модулю с заданной точностью.
Пункт 3 повторяется до тех пор, пока заданная точность не достигнута.

Код

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	double sum, eps, prev,next,dif;
	int i;
	eps=1e-10;
	prev=1; next=-1/3.0;
	i=2; 
	sum=1;
	dif=abs(next-prev);
	while (dif>eps){
		sum=sum+next;
		prev=next;
		next=-prev/((2*i+1)*i);
		i=i+1;
		dif=abs(prev-next);
	}
 	cout << "sum="<< sum << "\n" << endl;
 	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double sum, eps, prev,next,dif;

int i;

eps=1e-10;

prev=1; next=-1/3.0;

i=2;

sum=1;

dif=abs(next-prev);

while (dif>eps){

sum=sum+next;

prev=next;

next=-prev/((2*i+1)*i);

i=i+1;

dif=abs(prev-next);

}

cout << "sum="<< sum << "\n" << endl;

return 0;

}

Исправленный вариант

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	double sum, eps, A;
	cin >> eps;
	int i=1;
	A=-1/3.0;
	sum=A;
	while (abs(A)>eps){
		i++;
		A=A*(-2)/(2*i+3);
		sum+=A;
	}
 	cout << "sum="<< sum << endl;
 	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double sum, eps, A;

cin >> eps;

int i=1;

A=-1/3.0;

sum=A;

while (abs(A)>eps){

i++;

A=A*(-2)/(2*i+3);

sum+=A;

}

cout << "sum="<< sum << endl;

return 0;

}

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	double long sum, eps, A;
	cin >> eps;
	int i=0;
	A=-1/3.0;
	sum=A;
	while (abs(A)>=eps){
		i++;
		A=A*(-2)/((2*i+2)*(2*i+3));
		sum+=A;
	}
 	cout << "sum="<< sum << endl; 
 	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double long sum, eps, A;

cin >> eps;

int i=0;

A=-1/3.0;

sum=A;

while (abs(A)>=eps){

i++;

A=A*(-2)/((2*i+2)*(2*i+3));

sum+=A;

}

cout << "sum="<< sum << endl;

return 0;

}

Тесты

Входные данные (точность [latex]\epsilon [/latex])	Выходные данные (сумма ряда [latex]\sum_{i=1}^{\infty} (-1)^{i}\cdot \frac{2^{i}}{2\cdot i+1}[/latex])
e=1e-10	sum=-0.301544
e=0.0001	sum=-0.301543
e=0.001	sum=-0.301543
e=0.01	sum=-0.301587
e=0.1	sum=-0.3

Ссылки

условие задачи;
решение на ideone;
исправленное решение на ideone;
подсчёт суммы ряда в WolframAlpha;