Category Archives: 3. Циклические вычисления

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

Задачи

Найдите сумму цифр в десятичной записи целого числа
Найдите сумму цифр в десятичной записи целого числа, хранящегося при помощи класса java.math.BigInteger
Напишите функцию получения записи заданного числа в сбалансированной троичной системе счисления. (На вход поступает целое значение, на выходе — строка текста.)
Напишите функцию вычисления синуса при помощи разложения в ряд Тейлора и формул приведения. Точность вычисления должна быть максимально возможной для типа данных double.
Напишите функцию вычисления косинуса при помощи разложения в ряд Тейлора и формул приведения. Точность вычисления должна быть максимально возможной для типа данных double.
Напишите функцию вычисления тангенса при помощи разложения в ряд Тейлора и формул приведения. Точность вычисления должна быть максимально возможной для типа данных double.
Напишите функцию вычисления логарифма по натуральному основанию при помощи разложения в ряд Тейлора. Точность вычисления должна быть максимально возможной для типа данных double.

Более сложные задачи

Напишите функцию с тремя целочисленными параметрами [latex]n, m, k[/latex] для вычисления [latex]n^m \mod k[/latex]. Т.е. для вычисления остатка от деления на [latex]k[/latex] числа [latex]n[/latex] в степени [latex]m[/latex]. Постарайтесь сделать алгоритм быстрым.
Составить программу, выводящую на печать первые [latex]n[/latex] знаков числа [latex]\pi[/latex]. Число знаков может быть. Количество знаков задаётся переменной целого типа.
Для заданного натурального [latex]n[/latex] выведите последовательность чисел в которой нулевой элемент показывает сколько раз встретилось в этой же последовательности число ноль. Первый элемент — сколько раз встретилась единица. Второй — двойка и т.д. до [latex]n[/latex]. Обработайте ситуацию, когда такой последовательности нет.

e-olymp 127. Баксы в банке

04/07/2016 by Дарья Пиндус

Условие

Папа Карло подарил Буратино $1$ доллар в его первый день рождения, а экономный Буратино сложил подарок в банку. Каждый последующий год папа Карло удваивал свой предыдущий подарок и прибавлял к нему столько долларов, сколько лет исполнилось Буратино, а тот в свою очередь продолжал складывать баксы в банку. На какой $N$ -й день рождения в банке будет не менее чем $S$ долларов?

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

Единственное число – значение $S$ . $1\le S \le 240$ .

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

Искомое значение $N$ .

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

Тесты

Входные данные	Выходные данные
15	3
25	4
9	3
99	5
199	6
333	7
56	5
478	8
809	8

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone {
	public static void main(String[] args) {
        int startSum = 1;
        int years = 1;
        int k = 1;
        int currentSum = startSum;
 
        Scanner scanner = new Scanner(System.in);
        int sum = scanner.nextInt();
        while (currentSum < sum) {
            years++;
            k = k*2 + years;
            currentSum += k;
        }
        System.out.println(years);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main(String[] args) {

int startSum = 1;

int years = 1;

int k = 1;

int currentSum = startSum;

Scanner scanner = new Scanner(System.in);

int sum = scanner.nextInt();

while (currentSum < sum) {

years++;

k = k*2 + years;

currentSum += k;

}

System.out.println(years);

}

Решение

В данной задаче $sum$ – сколько долларов в банке, $p$ – сколько долларов Папа Карло подарил Буратино. Пока $sum<s$ мы увеличиваем $N$ на $1$ и считаем сколько Папа Карло подарит Буратино $p=p\cdot 2+n$ и суммируем его с тем что лежит в банке $sum += p$ .

Задача на Ideone.com

e-olymp 22. “Зеркально простые” числа

02/07/2016 by Артур Тарасов

Назовем число “зеркально простым”, если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.

Найти количество “зеркально простых” чисел на промежутке от [latex]a[/latex] до [latex]b.[/latex]

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

Два числа [latex]a[/latex] и [latex]b[/latex] [latex]( 1\le a, b \le 10000)[/latex].

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

Вывести количество “зеркально простых” чисел на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно.

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

Тесты

Границы промежутка	Количество “зеркально простых” чисел
1 10	4
100 200	12
1008 1230	19
3340 3950	31
9900 10000	4

Алгоритм

Перед нами была поставлена задача реализовать поиск всех “зеркально простых” чисел на заданном промежутке. Проверив в правильном ли порядке введены границы промежутка, организуем последовательный анализ для каждого числа из промежутка в теле главного цикла :

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

Достигнув верхней границы промежутка, выводим количество “зеркально простых” чисел.

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

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

class Main {
	public static void main (String[] args)	{
		int a, b;
    	int number1, number2;
	   	int counter = 0;
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();
		if (a > b) {
			a += b;
			b = a - b;
			a -= b;
		}
		if (a == 1) counter--;
		for (int i = a; i <= b; i++) {
			number1 = i; 
			boolean f1 = true;
			boolean f2 = true;
			for (int j = 2; j*j <= number1; j++) {					
				f1 = ((number1%j)!=0);
				if (!f1) 
				break;
			}
         	if (f1) {
				number2 = 0;
				while (number1 > 0) {
					number2 = number2*10 + number1%10;
					number1 /= 10;
				}
				for (int j = 2; j*j <= number2; j++) {
					f2 = ((number2%j)!=0);
					if (!f2) break; 
				}
             	if (f2) counter++; 
         	}
		}
		System.out.format("%d", counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

int a, b;

int number1, number2;

int counter = 0;

Scanner sc = new Scanner(System.in);

a = sc.nextInt();

b = sc.nextInt();

if (a > b) {

a += b;

b = a - b;

a -= b;

}

if (a == 1) counter--;

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

number1 = i;

boolean f1 = true;

boolean f2 = true;

for (int j = 2; j*j <= number1; j++) {

f1 = ((number1%j)!=0);

if (!f1)

break;

}

if (f1) {

number2 = 0;

while (number1 > 0) {

number2 = number2*10 + number1%10;

number1 /= 10;

}

for (int j = 2; j*j <= number2; j++) {

f2 = ((number2%j)!=0);

if (!f2) break;

}

if (f2) counter++;

}

System.out.format("%d", counter);

}

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

Засчитанное решение

e-olymp 29. Уровень палиндромности

02/07/2016 by Артур Тарасов

Задано натуральное [latex]M[/latex]. Если число не палиндром – записываем его в обратном порядка и слагаем с заданным. Действия повторяем до тех пор, пока не получим число-палиндром. Количество выполненных операций назовем уровнем палиндромности заданного числа.

Найти уровень палиндромности заданного числа [latex]M[/latex].

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

Единственное число [latex]M (0 < M < 10000)[/latex].

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

Единственное число – уровень палиндромности.

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

Тесты

Входные данные	Выходные данные
1	0
79	6
101	0
198	5
865	2
9998	6

Алгоритм

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

Для начала инициализируем счетчик, который хранит в себе текущее значение уровня палиндромности, и логическую переменную, значение которой ложно до тех пор пока палиндром не найден. Данное условие и будет критерием для выполнения тела основного цикла.
Присвоив значения переменным в цикле, выполняем последовательный разбор введенного числа на цифры и сборку “зеркального” числа.
Проверяем равенство числа и ему обратного.
Выполнение условного оператора сигнализирует о том, что палиндром найден, следовательно выводим “уровень”, изменяем значение логической переменной на противоположное и выходим из цикла.
В противном случае суммируем текущее число и “зеркальное”, инкрементируем счетчик.
Повторяем пункты 2, 3, 5 до истинности пункта 3 и перехода к 4.

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

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

class Main {
	public static void main (String[] args) {
		long x, x1, x2;
		long c;
		int k = 0;
		Scanner sc = new Scanner(System.in);
		x = sc.nextInt();
		boolean f = false;
		while (!f) {
			x1 = x;
			x2 = 0;
			while (x1 > 0) {
				c = x1 % 10;
				x1 /= 10;
				x2 = x2 * 10 + c;
			}
			if (x == x2) {
				System.out.format("%d", k);
				f = true; 
				break;
			} else { 
				x += x2;
				k++; 
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

long x, x1, x2;

long c;

int k = 0;

Scanner sc = new Scanner(System.in);

x = sc.nextInt();

boolean f = false;

while (!f) {

x1 = x;

x2 = 0;

while (x1 > 0) {

c = x1 % 10;

x1 /= 10;

x2 = x2 * 10 + c;

}

if (x == x2) {

System.out.format("%d", k);

f = true;

break;

} else {

x += x2;

k++;

}

Код программы
Засчитанное решение

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

01/07/2016 by Ирина Литвиненко

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

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

Сколько натуральных чисел из промежутка [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

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

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


class Main {
	
	public static void main (String[] args) throws java.lang.Exception {
		
		int sumMin, counter = 1;
		
		Scanner scanner = new Scanner(System.in);
		int m = scanner.nextInt();
		int n = scanner.nextInt();
		
		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++;
		}
		System.out.println(counter);
	}
	
	public static int sumOfDigits(int a){
		int sum = 0;
		while (a > 0) {
			sum += a%10;
			a /= 10;
		}
	return sum;
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

int sumMin, counter = 1;

Scanner scanner = new Scanner(System.in);

int m = scanner.nextInt();

int n = scanner.nextInt();

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

}

System.out.println(counter);

}

public static int sumOfDigits(int a){

int sum = 0;

while (a > 0) {

sum += a%10;

a /= 10;

}

return sum;

}

www.ideone.com

Решение
Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму [latex](sumMin)[/latex] сумме цифр первого числа [latex]M[/latex], счетчик количества элементов с минимальной суммой цифр изначально равен 1. В цикле подсчитываем сумму цифр каждого последующего числа, если найдется число с меньшей суммой цифр, значит теперь эта сумма и является минимальной, присваиваем её значение переменной [latex]sumMin[/latex]. Если же встречаются элементы, сумма цифр которых равна [latex]sumMin[/latex], увеличиваем счетчик. Он и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.
Ссылка на полностью засчитанное решение на сайте e-olymp.

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

01/07/2016 by Игорь Варламов

Задача на e-olymp 388

Ссылка на засчитанное решение.

Условие

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

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

Число [latex]n(1\leq n \leq10^{9}).[/latex]

Тесты

Входные данные(n)	Выходные данные
11	6
43	9
1	0

Код

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

class Main{
	public static void main (String[] args) throws java.lang.Exception{
		Scanner x = new Scanner(System.in);
		int counter = 0;
		int n = x.nextInt();
		while (n != 1) {
			counter++;
			if(n % 2 == 0){
				n = n / 2;
			} else {
				n++;
			}
		}
		System.out.print(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main{

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

Scanner x = new Scanner(System.in);

int counter = 0;

int n = x.nextInt();

while (n != 1) {

counter++;

if(n % 2 == 0){

n = n / 2;

} else {

n++;

}

System.out.print(counter);

}

Решение

Пусть [latex]n[/latex] – это число, которое мы будем изменять, а [latex]counter[/latex] – количество превращений. Цикл должен выполняться до того момента, пока [latex]n[/latex] Чтоб проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число – чётное, то делим его на 2, в противном случае – добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.

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

30/06/2016 by Иоанна Васильева

Задача на e-olimp.

Условие

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

Число $N$ (1 ≤ $N$ ≤ 10⁹).

Решение

Пусть $N$ – это число, которое мы будем изменять, а $counter$ – количество превращений. Цикл должен выполняться до того момента, пока $N \neq 1$ . Чтобы проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число – чётное, то делим его на 2, в противном случае – добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.

Код на Ideone.

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
  public static void main (String[] args) {
  	Scanner x = new Scanner(System.in);
	int n = x.nextInt();
	int counter = 0;
	if (n >= 1){
		while (n != 1) {
			counter++;
			if (n % 2 == 0) n = n / 2;
			else n++;
 		}
 		System.out.print(counter);
 	} else System.out.print( "Wrong number" );
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

Scanner x = new Scanner(System.in);

int n = x.nextInt();

int counter = 0;

if (n >= 1){

while (n != 1) {

counter++;

if (n % 2 == 0) n = n / 2;

else n++;

}

System.out.print(counter);

} else System.out.print( "Wrong number" );

}

Тест

Входные данные	Выходные данные
-5	Wrong number
1	0
6	4

Ссылка на решение на e-olimp.

Wallpainter

28/07/2015 by Valeriya Rud

Task

One construction company wants to minimize paint expenses. For this reason has to be made a program which can calculate an amount of a paint for the each order. Usually the owner know the longness L , wideness W , and highness H of the each room. Also one can of pain is good enough to paint 16 m², and the size of windows and doors are not important in this calculation

Input:

In the first line should be orders` amount. In the each next line — L, W, H and the wideness, longness, and highness are not more than 1000 .

Output:

For the each order will be shown one one number, what is required amount of the paint cans

Tests

Input	Output
2
8 8 2	4
1 1 3	1
10 6 2	4
11 6 2	5

Solution

Task «Repair» can be solved by using Data Strim processing.

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

class Main{
	public static void main (String[] args) throws java.lang.Exception{
		Scanner s = new Scanner(System.in);
		double order = s.nextDouble();
		for(int i = 0; i < order; i++){
			double l = s.nextDouble();
			double w = s.nextDouble();
			double h = s.nextDouble();
			int quantity =(int)Math.ceil(h * (l + w) / 8);
			System.out.println(quantity);
		}
	}
}

import java.util.*;

import java.io.*;

class Main{

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

Scanner s = new Scanner(System.in);

double order = s.nextDouble();

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

double l = s.nextDouble();

double w = s.nextDouble();

double h = s.nextDouble();

int quantity =(int)Math.ceil(h * (l + w) / 8);

System.out.println(quantity);

}

Matrix Transpose

17/07/2015 by Valeriya Rud

Транспонирование матрицы

Задача. Введите из стандартного потока матрицу и выведите её в транспонированном виде.

Number of operation

14/07/2015 by Valeriya Rud

Задача Определите количество операций сложения (+), вычитания (-) и умножения (*) в арифметическом выражении заданном строкой символов.
Протестировать задачу можно здесь.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Category Archives: 3. Циклические вычисления

Задачи

Более сложные задачи

e-olymp 127. Баксы в банке

Условие

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

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

Тесты

Код

Решение

e-olymp 22. “Зеркально простые” числа

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

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

Алгоритм

e-olymp 29. Уровень палиндромности

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

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

Алгоритм

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

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

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

Wallpainter

Task

Input:

Output:

Tests

Solution

Matrix Transpose

Транспонирование матрицы

Number of operation