Category Archives: 3. Циклы

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

Циклы

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

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

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

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

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

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

Ю3.45

25/09/2014 by Ілларіонова Марія Валеріївна

Ю3.45. Гуси и кролики. У гусей и кроликов вместе [latex]2n[/latex] лап. Сколько может быть гусей и кроликов (вывести все возможные сочетания)?

[latex]n[/latex]	Гусей.	Кроликов.	Комментарий.
4	0, 2, 4	2, 1, 0	Тест пройден.
3	1, 3	1, 0	Тест пройден.
0	0	0	Тест пройден.
7	1, 3, 5, 7	3, 2, 1, 0	Тест пройден.

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

#include <stdio.h>

int main(void) {
	int g, k, n; // Выбран тип int, так как это животные, и их количество может быть только целым неотрицательным числом. Гуси и кролики названы g и k соответственно.
	scanf ("%d", &n); // Ввод данных с клавиатуры.
	for (g=0; g<=n; g++) {
		for (k=0; k<=n/2; k++) {
			if (2*g + 4*k == 2*n) {
				printf ("Гусей - %d. \nКроликов - %d.\n\n", g, k);
			}
		}
	}
	return 0;
}

#include <stdio.h>

int main(void) {

int g, k, n; // Выбран тип int, так как это животные, и их количество может быть только целым неотрицательным числом. Гуси и кролики названы g и k соответственно.

scanf ("%d", &n); // Ввод данных с клавиатуры.

for (g=0; g<=n; g++) {

for (k=0; k<=n/2; k++) {

if (2*g + 4*k == 2*n) {

printf ("Гусей - %d. \nКроликов - %d.\n\n", g, k);

}

return 0;

}

Второй вариант с 1 циклом (C++):

#include <stdio.h>
 
int main(void) {
	int g, k, n; // Выбран тип int, так как это животные, и их количество может быть только целым неотрицательным числом. Гуси и кролики названы g и k соответственно.
	scanf ("%d", &n); // Ввод данных с клавиатуры.
	for (k=0; k<=n/2; k++) {
		g=(2*n-4*k)/2;
		printf ("Гусей - %d. \nКроликов - %d.\n\n", g, k);
	}
	return 0;
}

#include <stdio.h>

int main(void) {

scanf ("%d", &n); // Ввод данных с клавиатуры.

for (k=0; k<=n/2; k++) {

g=(2*n-4*k)/2;

printf ("Гусей - %d. \nКроликов - %d.\n\n", g, k);

}

return 0;

}

Java:

import java.util.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int g, k, n;
		Scanner in= new Scanner (System.in);
		n=in.nextInt();
		for (g=0; g<=n; g++) {
			for (k=0; k<=n/2; k++) {
				if (2*g + 4*k == 2*n) {
					System.out.format ("Гусей - %d. Кроликов - %d.%n", g, k);
				}
			}
		}
	}
}

import java.util.*;

import java.io.*;

class Ideone

{

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

{

int g, k, n;

Scanner in= new Scanner (System.in);

n=in.nextInt();

for (g=0; g<=n; g++) {

for (k=0; k<=n/2; k++) {

if (2*g + 4*k == 2*n) {

System.out.format ("Гусей - %d. Кроликов - %d.%n", g, k);

}

По условию задачи необходимо вывести все возможные варианты сочетаний количества кроликов и гусей.

Для того, чтобы это сделать, программа использует 2 цикла. В первом исследуется количество гусей: изначально переменной присваивается значение 0, затем следует условие продолжения (количество гусей не должно превышать [latex]n[/latex], то есть количество лап, делённое на 2).

После запуска первого цикла программа проверяет условие продолжения вложенного второго цикла (количество кроликов не превышает [latex]\frac{n}{2}[/latex]), в котором переменной [latex]k[/latex] также изначально присваивается значение 0. В случае выполнения условий обоих циклов программа проверяет, действительно ли количество лап гусей и кроликов в сумме даёт [latex]2n[/latex], заданных по условию задачи пользователем.

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

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

Протестировать решение можно по ссылкам: первое, второе (C++) и на Java.

Related Images:

Ю 3.14

21/09/2014 by Байков Дмитро

Задача

Проверить численно второй замечательный предел:[latex]\lim_{x\to\infty}\left(1+\frac{1}{n}\right)^n=e[/latex] , задавая n значения 1,2,3…При каком n исследуемое выражение отличается от e менее, чем на заданную погрешность [latex]\varepsilon[/latex]?

Тесты

[latex]\varepsilon[/latex]	n	Полученное e	e	Разность	Комментарий
1.1	1	2.0000000000	2.7182818284	0.7182818284	Пройден
0.005	271	2.7132834531	2.7182818284	0.0049983753	Пройден
0.0000000314	32890950	2.7182817970	2.7182818284	0.0000000313	Пройден
0	Погрешность равна 0, тогда e=2.7182818284, а n=бесконечность				Не пройден

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

import java.util.*;
import java.lang.*;
import java.io.*;
class Limit
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double ee, dife;//Описание переменных для хранения входных данных.//
		Scanner in = new Scanner(System.in);
		double E = Math.abs(in.nextDouble());//Чтение из стандартного потока ввода.// 
		int n = 0; //Присвоение значения переменной (от которой зависит цикл).//
		if (Math.abs(E) == 0)
		{
			System.out.printf("Погрешность равна 0, тогда e=" + Math.E + ", а n=infinity");
		}
		else
		{
			do //Сам цикл программы//
			{	
				n++;
				ee = Math.pow (1 + 1 / (double)n, (double)n); //Вычисление значения последовательности при n=1,2,3,..//
				dife = Math.E - ee; //Вычисление разности полученного значения и константы//
			}
			while (Math.abs(dife) > E); //Конечный критерий, при котором цикл останавливается//
			//Вывод окончательных результатов на экран//
			System.out.printf("После n=" + n + " исследуемое выражение отличается от е менее, чем на " + Math.abs(E) + ", а именно на " + dife + "\n"); 
			System.out.printf("Значение последовательности при таком n=" + ee + ", e=" + Math.E);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Limit

{

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

{

double ee, dife;//Описание переменных для хранения входных данных.//

Scanner in = new Scanner(System.in);

double E = Math.abs(in.nextDouble());//Чтение из стандартного потока ввода.//

int n = 0; //Присвоение значения переменной (от которой зависит цикл).//

if (Math.abs(E) == 0)

{

System.out.printf("Погрешность равна 0, тогда e=" + Math.E + ", а n=infinity");

}

else

{

do //Сам цикл программы//

{

n++;

ee = Math.pow (1 + 1 / (double)n, (double)n); //Вычисление значения последовательности при n=1,2,3,..//

dife = Math.E - ee; //Вычисление разности полученного значения и константы//

}

while (Math.abs(dife) > E); //Конечный критерий, при котором цикл останавливается//

//Вывод окончательных результатов на экран//

System.out.printf("После n=" + n + " исследуемое выражение отличается от е менее, чем на " + Math.abs(E) + ", а именно на " + dife + "\n");

System.out.printf("Значение последовательности при таком n=" + ee + ", e=" + Math.E);

}

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

Для этого в цикле высчитывалось значение формулы [latex](1+\frac{1}{n})^{n}[/latex] при [latex]n\to \infty[/latex] и находилась разность [latex]dife=e-(1+\frac{1}{n})^{n}[/latex]. Если[latex]dife>\varepsilon[/latex] , то цикл заканчивался и программа запоминала последнее значение n и после этого выводила его на экран.

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Limit
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double ee, dife;//Описание переменных для хранения входных данных.//
		Scanner in = new Scanner(System.in);
		double E = Math.abs(in.nextDouble());//Чтение из стандартного потока ввода.// 
		int n = 0; //Присвоение значения переменной (от которой зависит цикл).//
		if (Math.abs(E) == 0)
		{
			System.out.printf("Погрешность равна 0, тогда e=" + Math.E + ", а n=infinity");
		}
		else
		{
			do //Сам цикл программы//
			{	
				n++;
				ee = Math.pow (1 + 1 / (double)n, (double)n); //Вычисление значения последовательности при n=1,2,3,..//
				dife = Math.E - ee; //Вычисление разности полученного значения и константы//
			}
			while (Math.abs(dife) > E); //Конечный критерий, при котором цикл останавливается//
			//Вывод окончательных результатов на экран//
			System.out.printf("После n=" + n + " исследуемое выражение отличается от е менее, чем на " + Math.abs(E) + ", а именно на " + dife); 
			System.out.printf("Значение последовательности при таком n=" + ee + ", e=" + Math.E);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Limit

{

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

{

double ee, dife;//Описание переменных для хранения входных данных.//

Scanner in = new Scanner(System.in);

double E = Math.abs(in.nextDouble());//Чтение из стандартного потока ввода.//

int n = 0; //Присвоение значения переменной (от которой зависит цикл).//

if (Math.abs(E) == 0)

{

System.out.printf("Погрешность равна 0, тогда e=" + Math.E + ", а n=infinity");

}

else

{

do //Сам цикл программы//

{

n++;

ee = Math.pow (1 + 1 / (double)n, (double)n); //Вычисление значения последовательности при n=1,2,3,..//

dife = Math.E - ee; //Вычисление разности полученного значения и константы//

}

while (Math.abs(dife) > E); //Конечный критерий, при котором цикл останавливается//

//Вывод окончательных результатов на экран//

System.out.printf("После n=" + n + " исследуемое выражение отличается от е менее, чем на " + Math.abs(E) + ", а именно на " + dife);

System.out.printf("Значение последовательности при таком n=" + ee + ", e=" + Math.E);

}

Related Images:

Ю3.5

21/09/2014 by Ілларіонова Марія Валеріївна

Задача Ю3.5. Коммерция. Предприниматель, начав дело, взял кредит размером [latex]k[/latex] рублей, под [latex]p[/latex] процентов годовых и вложил его в своё дело. По прогнозам, его дело должно давать прибыль [latex]r[/latex] рублей в год. Сможет ли он накопить сумму, достаточную для погашения кредита, и если да, то через сколько лет?

[latex]k[/latex]	[latex]p[/latex]	[latex]r[/latex]	[latex]n[/latex]	Комментарий.
1800	50	1000	—	Кредит не будет погашен.
800000	15	40000	—	Кредит не будет погашен.
1000	5	400	3	Тест пройден.
1500	3,5	400	5	Тест пройден.

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

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

int main() {
	double p; // Для процентов определён тип дробных чисел.
	int k, n, r; // Для количества денег и лет определяем целочисленные значения.
	scanf ("%d %lf %d", &k, &p, &r); // Ввод данных с клавиатуры.
		for (n=1; (n*r)<(k*pow(1+(p/100), n)); n++) {
			if (k*pow(1+p/100, n)-k>=r) {
				puts ("You can't pay back a loan.\n");
				return 0;
			}
		}
		printf ("%d\n", n);
		
	return 0;
}

#include <stdio.h>

#include <math.h>

int main() {

double p; // Для процентов определён тип дробных чисел.

int k, n, r; // Для количества денег и лет определяем целочисленные значения.

scanf ("%d %lf %d", &k, &p, &r); // Ввод данных с клавиатуры.

for (n=1; (n*r)<(k*pow(1+(p/100), n)); n++) {

if (k*pow(1+p/100, n)-k>=r) {

puts ("You can't pay back a loan.\n");

return 0;

}

printf ("%d\n", n);

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double p, n=1.0, r; 
		int k;
		boolean f=false;
		Scanner in = new Scanner (System.in);
		k=in.nextInt();
		p=in.nextDouble();
		r=in.nextDouble();
		for (; (n*r)<(k*Math.pow(1+(p/100), n)); n++) {
			if (k*Math.pow(1+p/100, n)-k>=r) {
				System.out.println ("You can't pay back a loan.");
				f=true;
				break;
			}
		}
		if (f==false) {
			System.out.format ("%d%n", (int)n);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double p, n=1.0, r;

int k;

boolean f=false;

Scanner in = new Scanner (System.in);

k=in.nextInt();

p=in.nextDouble();

r=in.nextDouble();

for (; (n*r)<(k*Math.pow(1+(p/100), n)); n++) {

if (k*Math.pow(1+p/100, n)-k>=r) {

System.out.println ("You can't pay back a loan.");

f=true;

break;

}

if (f==false) {

System.out.format ("%d%n", (int)n);

}

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

Изначально запускается цикл, который основан на сравнении дохода за несколько лет [latex]nr[/latex] и размера кредита, которого он достигнет за эти годы (вычисляется по формуле сложных процентов: [latex]k(1+\frac{p}{100})^{n}[/latex]).

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

Проверить код можно здесь (C++) и здесь (Java).

Related Images:

Ю 3.4

19/09/2014 by Іванов Вячеслав Володимирович

Задача: Прямоугольник на плоскости [latex]a \le x \le b, \quad c \le y \le d[/latex] задаётся четырьмя числами (его габаритами): [latex]a, b, c, d.[/latex] Последовательно вводятся габариты [latex]n[/latex] прямоугольников. В процессе ввода находить площадь их пересечения, не запоминая самих габаритов.

NI — «no intersection» — нет общего сегмента

№	[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]d[/latex]	[latex]S[/latex]	Комментарий
1	-5	-3	1	4	NI	Пройден: нет общего интервала
-2	0	1	4
2	0	4.5	1.2	4.6	NI	Пройден: нет общего интервала
2	4	5	7.4
3	2	5	1	4	NI	Пройден: общая сторона не считается пересечением, т.к. даёт нулевую площадь
5	6	1	4
4	2	4	2	4	4	Пройден
2	4	2	4
5	2	5	1	4	NI	Пройден: не все данные прямоугольники имеют общий сегмент
0	3	2	3
6	7	3	5
6	0	7	0	3	1	Пройден
2	6	1	5
3	5	2	5
4	8	2	3

#include 
#include 
//sort pairs of coordinates by value
void sbv(double &x1, double &x2, double &y1, double &y2)
{
    if( x1 > x2 ) std::swap( x1 , x2 );
    if( y1 > y2 ) std::swap( y1 , y2 );
}
//find whether the rectangles intersect
bool intersect( double b1, double e1, double b2, double e2 )
{
    //"b" for "beginning", "e" for "end" (imagine the line segments on the coordinate axis)
    if( b2 >= e1 || e2 <= b1 ) return false;
    return true;
}

int main()
{
    double a, b, c, d; //meaningful coodinates of rectangle sides
    int n; scanf( "%d", &n );
    scanf( "%lg %lg %lg %lg", &a, &b, &c, &d );
    double x1 = a, x2 = b, y1 = c, y2 = d; //"x" and "y" pairs are for rectangle of common area
    for( int i=1; i<n; i++ )
    {
        scanf( "%lg %lg %lg %lg", &a, &b, &c, &d ); //refresh the coords.
        if( intersect( x1, x2, a, b ) && intersect( y1, y2, c, d ) ) //if they intersect
        {
            sbv( a, x1, x2, b ); //sort again to find the inner points
            sbv( c, y1, y2, d ); //(image is attached)
            printf("Common area of %d rectangles S = %lg\n", i+1, (y2-y1)*(x2-x1) );
        }
        else
        {
            printf("System of rectangles has no common area.\n");
            break;
        }

    }
    return 0;
}

#include

//sort pairs of coordinates by value

void sbv(double &x1, double &x2, double &y1, double &y2)

{

if( x1 > x2 ) std::swap( x1 , x2 );

if( y1 > y2 ) std::swap( y1 , y2 );

}

//find whether the rectangles intersect

bool intersect( double b1, double e1, double b2, double e2 )

{

//"b" for "beginning", "e" for "end" (imagine the line segments on the coordinate axis)

if( b2 >= e1 || e2 <= b1 ) return false;

return true;

}

int main()

{

double a, b, c, d; //meaningful coodinates of rectangle sides

int n; scanf( "%d", &n );

scanf( "%lg %lg %lg %lg", &a, &b, &c, &d );

double x1 = a, x2 = b, y1 = c, y2 = d; //"x" and "y" pairs are for rectangle of common area

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

{

scanf( "%lg %lg %lg %lg", &a, &b, &c, &d ); //refresh the coords.

if( intersect( x1, x2, a, b ) && intersect( y1, y2, c, d ) ) //if they intersect

{

sbv( a, x1, x2, b ); //sort again to find the inner points

sbv( c, y1, y2, d ); //(image is attached)

printf("Common area of %d rectangles S = %lg\n", i+1, (y2-y1)*(x2-x1) );

}

else

{

printf("System of rectangles has no common area.\n");

break;

}

return 0;

}

Алгоритм решения:
1. Для удобства, запрограммировать задачу можно, сведя её к одномерному случаю: рассматривать проекции сторон прямоугольников на координатные оси. (см. рис. 1)
2. Проверка на пересечение: данные прямоугольники пересекаются и имеют общую площадь, если их проекции имеют общий интервал значений, больший одной точки.
3. Так как запоминать габариты прямоугольников нельзя по условию, работать будем с габаритами «общего» прямоугольника, которые сохраняются соотв. в переменные [latex]x1 \le x2, y1 \le y2[/latex]. Если новый прямоугольник пересекается с «общим», то определить обновленные габариты общего прямоугольника и рассчитать площадь(см. рис. 2). Если не пересекается, то выполнение программы прерывается, т.к. нужно вывести площадь прямоугольника, общего для всех [latex]n[/latex] прямоугольников.

Значения переменных в условии задачи не ограничены, так что для хранения габаритов был использован тип double, для всех порядковых переменных — тип int.

Протестировать решение можно по ссылке.

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

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

Category Archives: 3. Циклы

Циклы

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

Ю3.45

Related Images:

Ю 3.14

Задача

Тесты

Related Images:

Ю3.5

Related Images:

Ю 3.4

Related Images: