e-olymp 8538. Калькулятор

27/11/2020 by Александр Розин

Условие

Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.

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

Одно число $n$ $\left(10\leq n\leq 10^9\right)$.

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

Выведите наименьшее количество операций.

Тесты

№	Входные данные	Выходные данные
1	1447	16
2	18	3
3	111	6

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

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 = in.nextInt();
		int k = 0;
		while(n > 0) {
			k += n%3 + 1;
			n /= 3;
		}
		System.out.print(k - 2);
	}
}

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 = in.nextInt();

int k = 0;

while(n > 0) {

k += n%3 + 1;

n /= 3;

}

System.out.print(k - 2);

}

Решение

Решим данную задачу от обратного. Пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл while(), который будет работать до тех пор, пока наше число $n$ будет строго больше $0$. Внутри цикла опишем следующее решение: пусть k будет счётчиком нажатий на кнопки калькулятора и изначально равняется $0$. Тогда, при каждом шаге цикла мы к счётчику будем прибавлять остаток от деления на $3$. n%3 — именно столько раз нам потребуется отнять $1$ от $n$ чтобы можно было нацело разделить на $3$. Далее, делим $n$ на $3$ и это потребует еще одного нажатия (что и происходит в строке $13$). Так как в условии цикла мы написали, что $n > 0$, то мы пройдём лишнюю итерацию и к счётчику прибавятся два лишних шага. Поэтому, при выводе ответа, от $k$ отнимаем $2$.

e-olymp 123. Количество нулей у факториала

10/09/2020 by Владислав Гринькив

Задача

Найти количество нулей в конце записи факториала числа $n$.

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

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

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

Количество нулей в конце записи $n!$

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	0
2	7	1
3	12	2
4	100	24
5	306	75
6	5000	1249

Код

class Main{
	public static void main (String[] args){
		java.util.Scanner in = new java.util.Scanner(System.in); 
		long n = in.nextInt(), m = 5, s = 0;
		while(n >= m){
			s = s + (n / m); 
			m = m * 5;
		}
		System.out.println(s);
	}
}

class Main{

public static void main (String[] args){

java.util.Scanner in = new java.util.Scanner(System.in);

long n = in.nextInt(), m = 5, s = 0;

while(n >= m){

s = s + (n / m);

m = m * 5;

}

System.out.println(s);

}

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

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

Код на Ideone

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

e-olymp 2814. Быстрое возведение в степень

31/03/2019 by Никита Пушкин

Задача

Быстрое возведение в степень

Очень часто возникает задача эффективного вычисления $x^{n}$ по данным $x$ и $n$, где $n$ — положительное целое число.
Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.
Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

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

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

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

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

#	Входные данные	Выходные данные
1	23	SSXSXSX
2	1
3	16	SSSS
4	1000000	SXSXSXSSXSSSSSXSSSXSSSSSS
5	2018	SXSXSXSXSXSSSSXS

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long n, k = 0, c = 0;
		Scanner S = new Scanner (System.in);
		n = S.nextLong();
		while (n > 1){
			long bit = n & 1;
			n >>= 1;
			k <<= 1;
			k |= bit;
			c += 1;
		}
		while (c != 0) {
			long bit = k & 1;
			k >>= 1;
			if (bit == 0) System.out.print("S");
			else System.out.print("SX");
			c -= 1;
		}
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

long n, k = 0, c = 0;

Scanner S = new Scanner (System.in);

n = S.nextLong();

while (n > 1){

long bit = n & 1;

n >>= 1;

k <<= 1;

k |= bit;

c += 1;

}

while (c != 0) {

long bit = k & 1;

k >>= 1;

if (bit == 0) System.out.print("S");

else System.out.print("SX");

c -= 1;

}

Решение

С помощью первого цикла while в переменную $k$ записываем перевернутый двоичный код числа $n$. Переменную $c$ используем как счётчик кол-ва бит в $n$. Во втором цикле while выводим S или SX если правый бит $0$ или $1$ соответственно, теряя при это последнюю $1$ как и сказано по условию задачи.

Условие задачи можно найти на e-olymp
Код решения — ideone

java@Cat

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

Tag Archives: цикл while

e-olymp 8538. Калькулятор

Условие

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

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

Тесты

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

Решение

e-olymp 123. Количество нулей у факториала

Задача

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

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

Тесты

Код

Решение

Ссылки

e-olymp 2814. Быстрое возведение в степень

Задача

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

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

Тесты

Решение