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]. Обработайте ситуацию, когда такой последовательности нет.

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

26/12/2018 by Андрей Лисовой

Задача

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

Вводные данные

Два положительных числа $n$ и $m$.

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

Все целые числа из $(0,n)$, удовлетворяющие условию.

Тесты

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

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
    	long n, m, t, sum;
    	n = in.nextLong(); 
    	m = in.nextLong();
    	for(long i = 1; i < n; i++) {
        	t = i;
        	sum = 0;
	        while(t != 0)
	            sum += t%10;
	            t /= 10;
	        }
        if(sum*sum == m) System.out.print(i + " ");
    	}
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

long n, m, t, sum;

n = in.nextLong();

m = in.nextLong();

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

t = i;

sum = 0;

while(t != 0)

sum += t%10;

t /= 10;

}

if(sum*sum == m) System.out.print(i + " ");

}

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

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

Ссылки

Условие задачи(страница 135)
Код решения на ideone.com

e-olymp 842. Разложение на простые множители

25/12/2018 by Иван Василевский

Условие задачи
Вывести представление целого числа $n$ в виде произведения простых чисел.
Входные данные
Единственное число $n (2 \leq n \leq 2^{31} — 1).$
Выходные данные
Вывести список простых множителей в порядке неубывания, разделённых знаком «$*$».
Тесты

Входные данные	Выходные данные
30	235
16	222*2
5	5

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        long numb, divisor = 2;
        numb = Integer.parseInt(params1[0]);
        while (divisor*divisor <= numb)
        {
            if (numb%divisor == 0)
            {
                System.out.print(divisor);
                numb = numb / divisor;
                System.out.print('*');
            }
            else if (divisor == 2) divisor = 3;
            else divisor = divisor + 2;
        }
        System.out.print(numb);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

long numb, divisor = 2;

numb = Integer.parseInt(params1[0]);

while (divisor*divisor <= numb)

{

if (numb%divisor == 0)

{

System.out.print(divisor);

numb = numb / divisor;

System.out.print('*');

}

else if (divisor == 2) divisor = 3;

else divisor = divisor + 2;

}

System.out.print(numb);

}

Решение задачи
Пока наше число больше либо равно divisor*divisor выполняется:

Если numb делится нацело на divisor, мы выводим наш делитель, следовательно numb делится на divisor;
В противном случае:

Если divisor равен $2$ , то присваиваем ему значение $3$ и повторяем;
В другом случае увеличиваем его на $2$;

Таким образом перебираются $2$,$3$ и $5$, которые являются делителем для всех чисел.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 1494. Санта Клаус

23/12/2018 by Томас Пасенченко

Задача

Санта Клаус готовится к Рождеству. В этот праздник он хочет вручить подарки $n$ детям. Его помощники Эльфы уже собрали два мешка, с которыми он отправится в новогоднее путешествие по всем странам мира. И чтобы Санта не запутался, Эльфы составили список детей, чьи подарки уже лежат в каждом из мешков. Санта хочет помочь Эльфам, и поэтому решил положить в третий мешок подарки для тех детей, которым они еще не подготовлены.

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: $n$ — число детей, $m$ и $k$ — число подарков в первом и втором мешке соответственно $(1\leq n,\;m,\;k\leq 100;m+k\leq n)$. Вторая строка входного файла содержит $m$ целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит $k$ целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими $n$. Все дети должны получить подарок на Рождество, иначе Санта расстроится.

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

В первой строке выведите одно число $a$ — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке $a$ чисел — номера детей, которым эти подарки должны быть доставлены.

Тесты

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

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

import java.util.Scanner;
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int k = scanner.nextInt();
		int num;
		boolean children[] = new boolean[n];
		for (int i = 0; i < n; i++) {
			children[i] = false;
		}
		for (int i = 0; i < m + k; i++) {
			num = scanner.nextInt();
			num--;
			children[num] = true;
		}
		System.out.println(n - m - k);
		for (int i = 0; i < n; i++) {
			if (!children[i]) {
				System.out.print((i + 1) + " ");
			}
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int m = scanner.nextInt();

int k = scanner.nextInt();

int num;

boolean children[] = new boolean[n];

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

children[i] = false;

}

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

num = scanner.nextInt();

num--;

children[num] = true;

}

System.out.println(n - m - k);

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

if (!children[i]) {

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

}

Решение

Создадим массив типа boolean , в котором каждому $i$-ому ребёнку соответствует элемент с индексом $i-1$ , принимающий значение $0$, если для ребёнка ещё нет подарка, и $1$, если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

Условие задачи на e-olymp
Решение на ideone
Решение на e-olymp

e-olymp 9. N-значные числа

23/12/2018 by Андрей Лисовой

Задача

Найти количество $N$-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного $(N<10).$

Вводные данные

Число не превышающее $N.$

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

В выходном файле через пробел вывести $2$ числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные	Выходные данные
$1$	$10$ $0$
$2$	$1$ $22$
$4$	$12$ $1124$
$5$	$40$ $11125$
$9$	$144$ $111111129$

Код программы(Цикл)

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

class Main {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner in = new Scanner(System.in);
		double n = in.nextDouble();
		boolean minNumberPrinted = false;
		int count = 0;
		int minNumber = 0;
		if(n == 1) System.out.println(10 + " " + 0);
		else {
			if(n>1 & n<8) {
				for(int i = (int)Math.pow(10, n-1); i  0) {
						int digit = number % 10;
						sum += digit;
						mult *= digit;
						number /= 10;
					}
					if(sum == mult & minNumberPrinted == false) {
						minNumber = i;
						count++;
						minNumberPrinted = true;
					}
					else {
						if(sum == mult) count++;
					}
				}
				System.out.print(count + " " + minNumber);
			}
			else {
				if(n == 8) System.out.print(224 + " " + 11111128);
				if(n == 9) System.out.print(144 + " " + 111111129);
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

Scanner in = new Scanner(System.in);

double n = in.nextDouble();

boolean minNumberPrinted = false;

int count = 0;

int minNumber = 0;

if(n == 1) System.out.println(10 + " " + 0);

else {

if(n>1 & n<8) {

for(int i = (int)Math.pow(10, n-1); i 0) {

int digit = number % 10;

sum += digit;

mult *= digit;

number /= 10;

}

if(sum == mult & minNumberPrinted == false) {

minNumber = i;

count++;

minNumberPrinted = true;

}

else {

if(sum == mult) count++;

}

System.out.print(count + " " + minNumber);

}

else {

if(n == 8) System.out.print(224 + " " + 11111128);

if(n == 9) System.out.print(144 + " " + 111111129);

}

Решение задачи(Цикл)

Для cлучаев, когда $N=1,$ $N=8$ и $N=9$ сделаем отдельные ситуации и выведем сразу результат, т.к. эти значения долго считаются в основном цикле. Для случаем, когда $1<N<8$ создадим цикл, который создает последовательность $N$-значных чисел. Затем в цикле while (number > 0) считаем сумму и произведение цифр каждого числа из последовательности. Если сумма и произведение равны и переменная minNumberPrinted равна false, (т.e. не найдено еще минимальное число из этой последовательности, что его сумма и произведение цифр равны), то переменной minNumber присвоим минимальное найденное число. Иначе, если сумма и произведение цифр числа равно, просто прибавляем счетчику $1.$ Выводим полученный результат. Задача решена.

Код программы (Массив)

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
    	int[] x = {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
    	int n;
    	n = in.nextInt();
    	System.out.print(x[2*n-2] + " " + x[2*n-1]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int[] x = {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};

int n;

n = in.nextInt();

System.out.print(x[2*n-2] + " " + x[2*n-1]);

}

Решение задачи(Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив x. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — $2n-2,$ для минимального числа — $2n-1.$ Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения 1 на ideone.com (цикл)
Код решения 1 на ideone.com (массив)

e-olymp 165. Симметрия

16/12/2018 by Даниил Крутоголов

Задача

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

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

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

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]10[/latex]	[latex]2[/latex]
2	[latex]116[/latex]	[latex]3[/latex]
3	[latex]1[/latex]	[latex]1[/latex]
4	[latex]454[/latex]	[latex]2[/latex]
5	[latex]12301230[/latex]	[latex]2[/latex]

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

import java.util.Scanner;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		double k;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = (int)(Math.log(n)/Math.log(2));
		k = (double)(Math.log(n)/Math.log(2));
		while (m != k){
			n = (int)(n - (Math.pow(2,m)));
			m = (int)(Math.log(n)/Math.log(2));
			k = (double)(Math.log(n)/Math.log(2));
		}
	System.out.print(m + 1);
	}
}

import java.util.Scanner;

class Main

{

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

{

int n, m;

double k;

Scanner scan = new Scanner(System.in);

n = scan.nextInt();

m = (int)(Math.log(n)/Math.log(2));

k = (double)(Math.log(n)/Math.log(2));

while (m != k){

n = (int)(n - (Math.pow(2,m)));

m = (int)(Math.log(n)/Math.log(2));

k = (double)(Math.log(n)/Math.log(2));

}

System.out.print(m + 1);

}

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

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

15/12/2018 by Георгий Мартынюк

h1>Задача

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

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

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

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

Вывести количество страниц в книге.

Тесты

Входные данные	Выходные данные
27	18
15	12
9	9
49	29
50	0

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n, m, minus = 1;
		n = in.nextInt();
		m = 1;
		for  (int a = 1; n> 0; a *= 10) {
		  for  (int b = a; b < a*10; b++) {
			if ((n - minus) < 0) {
			  System.out.print(0);
			  return;
			}
			if ((n - minus) == 0) {
				System.out.print(m);
			  return;
			}
			n-= minus;
			m++;
		  }
		  minus++;
		}
		in.close();
		return;
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n, m, minus = 1;

n = in.nextInt();

m = 1;

for (int a = 1; n> 0; a *= 10) {

for (int b = a; b < a*10; b++) {

if ((n - minus) < 0) {

System.out.print(0);

return;

}

if ((n - minus) == 0) {

System.out.print(m);

return;

}

n-= minus;

m++;

}

minus++;

}

in.close();

return;

}

Решение

Для решения этой задачи я описал [latex]3[/latex] переменные: [latex]n[/latex], [latex]m[/latex] и [latex]minus[/latex], где [latex]n[/latex]- количество цифр, использованных для нумерации страниц, [latex]m[/latex] — количество страниц и [latex]minus[/latex] — «счетчик», для определения количества цифр в числе [latex]a[/latex]. Использовал [latex]2[/latex] вложенных цикла, где счетчик [latex]a[/latex] — определяет разрядность числа страницы [latex]b[/latex]. Внутри вложенного цикла перед вычитанием [latex]minus[/latex] из [latex]n[/latex] поставил проверку на выполнения условий: если [latex]n==0[/latex], значит мы закончили считать страницы и если [latex]n-minus<0[/latex], значит на следующей итерации мы запишем [latex]n[/latex] в отрицательное значение, значит во входных данных была ошибка.

Ссылки

Ideone
e-olymp

e-olymp 2817. Двоичные числа

14/12/2018 by Павел Жуков

Задача

Для заданного положительного целого числа $n$, распечатать позиции всех $1$ в двоичном его представлении. Позиция младшего бита имеет номер $0$.
Позиции $1$ в двоичном представлении числа $13$ — это $0$, $2$, $3$.
Напишите программу, которая для каждого набора данных:

читает натуральное число $n$,
вычисляет позиции $1$ в двоичном представлении $n$,
выводит результат.

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

В первой строке входного файла содержится одно натуральное число $d$, указывающее количество наборов входных данных, $1 \leq d \leq 10$. Входные данные заданы ниже.

Каждый набор данных состоит ровно из одной строки, содержащей ровно одно целое число $n$, $0 \leq n \leq 10^6$.

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

Вывод должен состоять ровно из $d$ строк — по одной строке для каждого набора входных данных.

Строка $i$, $1 \leq i \leq d$, должна содержать возрастающую последовательность целых чисел, разделенных одним пробелом — позиции $1$ в двоичном представлении $i$-го числа, полученного во входных данных.

Тесты

Входные данные	Выходные данные
$3$ $17$ $7$ $5$	$0$ $4$ $0$ $1$ $2$ $0$ $2$
$4$ $1945$ $1337$ $1000000$ $999999$	$0$ $3$ $4$ $7$ $8$ $9$ $10$ $0$ $3$ $4$ $5$ $8$ $10$ $6$ $9$ $14$ $16$ $17$ $18$ $19$ $0$ $1$ $2$ $3$ $4$ $5$ $9$ $14$ $16$ $17$ $18$ $19$
$10$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$	$0$ $1$ $0$ $1$ $2$ $0$ $2$ $1$ $2$ $0$ $1$ $2$ $3$ $0$ $3$

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String[] params1 = bufferedReader.readLine().split(" ");
		int d;
		d = Integer.parseInt(params1[0]);
		for (int j = 0; j < d; ++j){ String[] params2 = bufferedReader.readLine().split(" "); int n; boolean w = false; n = Integer.parseInt(params2[0]); for (int i = 0; n>0; ++i){
				if (n % 2 == 1){
					if(w){
						System.out.print(" ");
					}
					w = true;
					System.out.print(i);
				}
				n /= 2;
			}
			System.out.print("\n");
		}
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

int d;

d = Integer.parseInt(params1[0]);

for (int j = 0; j < d; ++j){ String[] params2 = bufferedReader.readLine().split(" "); int n; boolean w = false; n = Integer.parseInt(params2[0]); for (int i = 0; n>0; ++i){

if (n % 2 == 1){

if(w){

System.out.print(" ");

}

w = true;

System.out.print(i);

}

n /= 2;

}

System.out.print("\n");

}

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

Для решения этой задачи нужно понять, что остаток от деления $n$ на $2$ это последняя цифра в двоичном коде числа $n$, а деление целочисленной переменной $n$ на $2$ это отбрасывание последней цифры в двоичном коде. Цикл с счетчиком $i$ до момента, как $n$ не станет равняться $0$, очевиден, как и внешний цикл от $0$ до $d$, который реализовывает $d$ итераций ввода числа $n$. Стоит отметить, что тесты на e-olymp (все, кроме первого) чувствительны к пробелам в конце строки, из-за чего появляется необходимость каким-то образом его избежать.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

e-olymp 7457. Max-Min в двійковій системі счислення

06/12/2018 by Саша Рябова

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом $N$ знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

$N=13_{10}$, в двійковій системі числення — $1101_2$, найбільше число $1110_2 = 14_{10}$, найменше число $0111_2 = 7_{10}$. $14−7=7$.

Вхідні дані

В єдиному рядку записане число $N (N<2^{31})$.

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані	Вихідні дані
2	1
15	0
86	105
1000	945
40	45

Код програми

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

class Main
{
	 public static double max_number(int n1, int n0){
	 	double number = 0;
    	for (int i = n0+n1-1; i >= n0; i = i-1)
    	{
        	number += Math.pow(2, i);  
    	}
    	return (number);
	}
	public static double min_number(int n1, int n0)
	{
	    double  number = 0;
	    for (int i = n1-1; i >= 0; i = i-1)
	    {
	        number = number + Math.pow(2, i);  
	    }
	    return(number);
	}
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner in = new Scanner(System.in);
        int n = in.nextInt();
	    int n1=0;
	    int n0=0;
	    while (n>0)
	    {
	        if (n%2==1){
	        	n1=n1+1;
	        	}
	        else{
	        	n0+=1;
	        }
	        n/=2;
	    }
	    int res = (int) max_number(n1, n0) - (int) min_number(n1, n0);
	    System.out.print(res);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static double max_number(int n1, int n0){

double number = 0;

for (int i = n0+n1-1; i >= n0; i = i-1)

{

number += Math.pow(2, i);

}

return (number);

}

public static double min_number(int n1, int n0)

{

double number = 0;

for (int i = n1-1; i >= 0; i = i-1)

{

number = number + Math.pow(2, i);

}

return(number);

}

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int n1=0;

int n0=0;

while (n>0)

{

if (n%2==1){

n1=n1+1;

}

else{

n0+=1;

}

n/=2;

}

int res = (int) max_number(n1, n0) - (int) min_number(n1, n0);

System.out.print(res);

}

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа $n$.
Створимо функцію $max_number$, яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
Створимо функцію $min_number$, яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
Виведемо на екран різницю підрахованих функціями $max_number$ та $min_number$ значень.

Посилання

Умова на e-olymp
Вирішення мовою C++ з поясненнями
Код на java

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

04/12/2018 by Костя Григорян

Задача

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

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

Два положительных числа $n$ и $m$.

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

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

Тесты

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

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

import java.util.Scanner;
 
public class Main {
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		for(int i=1; i<n; i++) {
			int a=i;
			int sum=0;
			while(a!=0) {
				sum+=a%10;
				a/=10;
			}
			if(sum*sum==m)
				System.out.print(i+" ");
		}
	}
}

import java.util.Scanner;

public class Main {

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int m = scanner.nextInt();

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

int a=i;

int sum=0;

while(a!=0) {

sum+=a%10;

a/=10;

}

if(sum*sum==m)

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

}

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

Находим сумму цифр каждого числа от $1$ до $n$, проверяя равняется ли эта сумма, возведенная в квадрат, числу $m$. В случае положительного ответа, выводим число, сумму цифр которого мы проверяли.

Ссылки

Условие задачи (страница 135)
Код решения

e-olymp 2807. Кубики-3

03/12/2018 by Валерия Ларикова

Задача

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

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

В первой строке задано количество найденных Витеком кубиков [latex]n[/latex] [latex](1 \leqslant n \leqslant 10^5),[/latex] а во второй строке n символов, изображённых на каждом из кубиков

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

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex]»Ok»,[/latex] если Витек ошибся и ни один из кубиков не потерялся.

Тесты

#	Входные данные	Выходные данные
1	5 abcac	b
2	8 ryirhiyh	Ok
3	3 AVA	V
4	6 DjkjDk	Ok
5	7 LnCsCnL	s

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

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

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s = in.next();
		char res = 0;
		for(int i = 0; i < n; i++)
			res ^= s.charAt(i);
		if (res == 0)
			System.out.println("Ok");
		else 
			System.out.printf("%c\n",res);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String s = in.next();

char res = 0;

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

res ^= s.charAt(i);

if (res == 0)

System.out.println("Ok");

else

System.out.printf("%c\n",res);

}

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

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Воспользуемся оператором присваивания побитового исключающего или, с помощью которого мы будем сравнивать индексы символов, полученные из массива строки. Если количество кубиков четное, то переменная [latex]res[/latex] будет равна нулю, следовательно не один из кубиков не потерялся и мы увидим сообщение с текстом [latex] «Ok»[/latex]. Иначе выводится символ, который изображен на потерянном кубике.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Задача

Вводные данные

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

Тесты

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

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

Ссылки

30

2*3*5

16

2*2*2*2

5

5

Задача

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

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

Тесты

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

Решение

Ссылки

Задача

Вводные данные

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

Тесты

Код программы(Цикл)

Решение задачи(Цикл)

Код программы (Массив)

Решение задачи(Массив)

Ссылки

Задача

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

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

Тесты

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

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

Ссылки

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

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

Тесты

Решение

Ссылки

Задача

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

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

Тесты

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

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

Ссылки

Умова

Пояснення

Вхідні дані

Вихідні дані

Тести

Код програми

Рішення

Посилання

Задача

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

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

Тесты

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

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

Ссылки

Задача

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

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

Тесты

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

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

Ссылки

235

222*2