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

А116г

29/06/2017 by Шостак Дмитрий

Задача

Даны натуральное число [latex]n[/latex] и действительное число [latex]x[/latex]. Вычислить [latex]\prod\limits_{k = 1}^n (1+\frac{\sin(kx)}{k!})[/latex].

Тесты

№	n	x	Произведение
1	4	3.22	0.9673
2	11	214.3	2.8177
3	1	14	1.9906
4	7	0.76	2.8456

Решение

class ThirdLab
{
	public static void main (String[] args)
	{
		Scanner input = new Scanner(System.in);
		double x, mult = 1;
		int n, k, fact = 1;
		
		n = input.nextInt();
		x = input.nextDouble();
		
		for(k = 1; k <= n; k++)
		{
			fact *= k;
			mult *= 1 + (Math.sin(k*x)/fact);
		}
		
		System.out.printf("%.4f", mult);
	}
}

class ThirdLab

{

public static void main (String[] args)

{

Scanner input = new Scanner(System.in);

double x, mult = 1;

int n, k, fact = 1;

n = input.nextInt();

x = input.nextDouble();

for(k = 1; k <= n; k++)

{

fact *= k;

mult *= 1 + (Math.sin(k*x)/fact);

}

System.out.printf("%.4f", mult);

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Для вычисления данного в условии произведения кроме действительного x и натурального n введем такие переменные: mult — переменная произведения для вычисления в цикле, fact — переменная факториала [latex]k[/latex].

Инициализируем переменные n и x значениями из потока ввода, после чего создаем цикл по [latex]k[/latex] от 1 до [latex]n[/latex], в котором будет вычисляться факториал и, собственно, само произведение. При вычислении произведения используем функцию sin() стандартной библиотеки Math. По завершению цикла, выводим произведение с точностью до четырёх символов после запятой.

MLoop 15. Циклические вычисления

28/05/2017 by Anh Tuan

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

x	$latex \varepsilon$	Результат
42	0.3	-8.09848e-05
8	0.15	-0.0117188
55.5	0.04	-3.50972e-055
-12	0.6	0.00347222
-82	0.0001	-3.23677e-08

package lab3; 
import java.util.Scanner;
public class Lab3 
{ 
    public static void main(String[] args) 
    {
        Scanner scanIn = new Scanner(System.in);
        double x, e; 
        x = scanIn.nextDouble(); 
        e = scanIn.nextDouble();
        double sum1 = x; // в случае, когда  i=0
        double sum2 = -x * x * x / 6; // в случае, когда i=1
        for (int i = 2; Math.abs(1 / sum2 - 1 / sum1) >= e; i++) 
        {
            sum1 = sum2;
            sum2 *= -x * x / ((2 * i) * (2 * i + 1)); 
        }

        System.out.println("1 / sum2: " + 1 / sum2);
    }
}

package lab3;

import java.util.Scanner;

public class Lab3

{

public static void main(String[] args)

{

Scanner scanIn = new Scanner(System.in);

double x, e;

x = scanIn.nextDouble();

e = scanIn.nextDouble();

double sum1 = x; // в случае, когда i=0

double sum2 = -x * x * x / 6; // в случае, когда i=1

for (int i = 2; Math.abs(1 / sum2 - 1 / sum1) >= e; i++)

{

sum1 = sum2;

sum2 *= -x * x / ((2 * i) * (2 * i + 1));

}

System.out.println("1 / sum2: " + 1 / sum2);

}

Решение
Косеканс — это тригонометрическая функция, которою можно определить формулой $latex \csc x=\frac{1}{\sin x}$

. Таким образом, мы можем разложить функцию

в бесконечную сумму степенных функций, воспользовавшись формулой Тейлора. Получим, что $latex \sin x=x-\frac{{x}^{3}}{3!}+\frac{{x}^{5}}{5!}-\dots=\sum_{n=0}^{\propto}\frac{{-1}^{n}\times{x}^{2n+1}}{\left(2n+1\right)!}$

. Слагаемые данной суммы являются геометрической прогрессией, знаменатель который можно найти по формуле $latex \frac{a_n}{a_{n-1}}=\frac{\frac{{-1}^{n}\times{a}^{2n+1}}{\left(2n+1 \right)!}}{\frac{{-1}^{n-1}\times{a}^{2n-1}}{\left(2n-1 \right)!}}=\frac{\left( -1\right){a}^{2}}{2n\times\left( 2n+1\right)}$

. Будем вычислять сумму до тех пор, пока разность

-го и

-го слагаемых будет больше заданной точности.

Ideone.com

MLoops 17

23/11/2016 by Коваль Максим

Задача

+++++++++++++++++++++++++++++++
+....^....+....^....+....^....+
+....|....+....|....+....|....+
+<-- k -->+<-- k -->+<-- k -->+
+....|....+....|....+....|....+
+....v....+....v....+....v....+
+++++++++++++++++++++++++++++++
+....^....+....^....+....^....+
+....|....+....|....+....|....+
+<-- k -->+<-- k -->+<-- k -->+
+....|....+....|....+....|....+
+....v....+....v....+....v....+
+++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++

+....^....+....^....+....^....+

+....|....+....|....+....|....+

+<-- k -->+<-- k -->+<-- k -->+

+....|....+....|....+....|....+

+....v....+....v....+....v....+

+++++++++++++++++++++++++++++++

+....^....+....^....+....^....+

+....|....+....|....+....|....+

+<-- k -->+<-- k -->+<-- k -->+

+....|....+....|....+....|....+

+....v....+....v....+....v....+

+++++++++++++++++++++++++++++++

Тесты

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

m	n	k
13	31	9

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

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

+++++++++++++++++++++++++++++++

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

+++++++++++++++++++++++++++++++

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

+++++++++++++++++++++++++++++++

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

m	n	k
5	8	4

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

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

++++++++

+....+..

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

m	n	k
20	20	3

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

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

++++++++++++++++++++

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

++++++++++++++++++++

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

++++++++++++++++++++

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

++++++++++++++++++++

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

Алгоритм

Программа выполняется с помощью двух циклов. Первый цикл отвечает за строки, второй за столбцы. Метод заключается в том, чтобы узнать, когда мы записываем именно ‘+’, а уже в остальные места записываем ‘.’. Для начала проверяем делится ли номер строки, уменьшенный на 1, нацело на 6. Если да, то записываем +. Далее проверяем, делится ли номер столбца, уменьшенный на 1, на число $k+1$ , где $k$ — вводимый параметр. Во всех остальных случаях пишем ‘.’.

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

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

class Ideone 
{
	public static void main (String[] args){
                Scanner sc = new Scanner(System.in);
                int m,n,k;
                m = sc.nextInt();
                n = sc.nextInt();
                k = sc.nextInt();
                for (int i = 0; i < m; i++){
                     for (int j = 0; j < n; j++){
                             if (i%6 == 0) 
                                  System.out.print("+");
                             else if (j%(k+1) == 0) 
                                  System.out.print("+");
                             else 
                                  System.out.print(".");
                     }
                     System.out.println(" ");
                }
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import static java.lang.Math.*;

class Ideone

{

public static void main (String[] args){

Scanner sc = new Scanner(System.in);

int m,n,k;

m = sc.nextInt();

n = sc.nextInt();

k = sc.nextInt();

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

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

if (i%6 == 0)

System.out.print("+");

else if (j%(k+1) == 0)

System.out.print("+");

else

System.out.print(".");

}

System.out.println(" ");

}

Ссылка на Ideone

http://ideone.com/9QGk0A

А694а

14/11/2016 by Рыжков Саша

Задача
Получить квадратную матрицу порядка $n$
$\begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}$

Тесты

n	Матрица
3	1 0 0 0 1 0 0 0 1
4	1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
6	1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1

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

public class А694а {
    public static void main(String[] args) {
         int n;
         Scanner sc = new Scanner(System.in); 
         n=sc.nextInt();
         int[][] matrix;
         matrix = new int[n][n];
         for(int i=0;i &lt; n;i++){
            matrix[i][i]=1;
         }
         for(int i=0;i&lt;n;i++){
            for(int y=0;y&lt;n;y++){
                if(matrix[i][y]!=1){
                    matrix[i][y]=0;
                }
            }
         }
         for(int i=0;i&lt;n;i++){
            for(int y=0;y&lt;n;y++){
                System.out.print(matrix[i][y]);
            }
             System.out.println(&quot;\n&quot;);
         }
    }    
}

public class А694а {

public static void main(String[] args) {

int n;

Scanner sc = new Scanner(System.in);

n=sc.nextInt();

int[][] matrix;

matrix = new int[n][n];

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

matrix[i][i]=1;

}

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

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

if(matrix[i][y]!=1){

matrix[i][y]=0;

}

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

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

System.out.print(matrix[i][y]);

}

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

}

Ход работы:

1. С помощью цикла заполняем главную диагональ единицами.

2. Приравниваем элементы не равные единице к нулю.

3. Вывод массива.

Ссылка на ideone

A410e

16/10/2016 by Эдуард Брагар

Дана целочисленная матрица [latex]\begin{bmatrix}a_{i,j}\end{bmatrix},i,j=1,..,n[/latex].Получить [latex]b_{1},..,b_{n}[/latex],где [latex]b_{i}[/latex] — это:

[latex]\underset{1\leq j\leq n}{\max a_{ij}}\ * \underset{1\leq j\leq n}{\min a_{ji}}[/latex]

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex] -го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1} = 2[/latex], [latex]b_{2} = 4[/latex].

    import java.util.*;
    import java.lang.*;
    import java.io.*;
     
    /* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception{
		Scanner in = new Scanner(System.in);
		int n,maxa,mina;
		n = in.nextInt();
		int a[][] = new int[n][n];
		
		for(int i = 0 ; i < n; ++i){
			for(int j = 0; j < n; ++j) {
				a[i][j] = in.nextInt();
			}
		}
		
		int b[] = new int[n];
		
		for( int i = 0; i < n; ++i ) {
		
			maxa = a[i][0]; //Придаем максимуму значение первого элемента i-й строки.
			mina = a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.
		
			for( int j = 0; j < n; ++j ) {
				maxa = (maxa > a[i][j] ? maxa : a[i][j]); //Вычисляем максимум i-й строки.
				mina = (mina < a[j][i] ? mina : a[j][i]); //Минимум i-го столбца.
			}
		
			b[i] = maxa * mina; //Наш результат.
		}	
			
		for( int i = 0; i < n; ++i ){
			System.out.print( b[i] + " " );
		}	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

Scanner in = new Scanner(System.in);

int n,maxa,mina;

n = in.nextInt();

int a[][] = new int[n][n];

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

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

a[i][j] = in.nextInt();

}

int b[] = new int[n];

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

maxa = a[i][0]; //Придаем максимуму значение первого элемента i-й строки.

mina = a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.

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

maxa = (maxa > a[i][j] ? maxa : a[i][j]); //Вычисляем максимум i-й строки.

mina = (mina < a[j][i] ? mina : a[j][i]); //Минимум i-го столбца.

}

b[i] = maxa * mina; //Наш результат.

}

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

System.out.print( b[i] + " " );

}

Тесты

Матрица порядка [latex]n[/latex], где [latex]n[/latex]:	[latex]a[i][j][/latex]	Результат
2	[latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex]	2 4
3	[latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex]	3 -8 -6

Решение

Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ij}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

http://ideone.com

e-olymp 904. Увеличить на 2

11/10/2016 by Эдуард Брагар

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

Задан одномерный массив [latex]A[/latex] целых чисел. Увеличить на [latex]2[/latex] каждый неотрицательный элемент массива.

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

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

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

В единственной строке вывести через пробел [latex]n[/latex] чисел: новые значения элементов массива, в том же порядке, в котором они были заданы.

Код

import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
	public static void main (String[] args) {
		
		Scanner in = new Scanner(System.in);
			
		int n = in.nextInt();
		int a = 0;
			
		for(int i = 0; i < n; i++){
			a = in.nextInt();
			System.out.printf("%d", (a < 0)? a : a + 2);	
		}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int a = 0;

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

a = in.nextInt();

System.out.printf("%d", (a < 0)? a : a + 2);

}

Тесты

Входные данные	Выходные данные
4 1 2 3 4	3 4 5 6
4 1 2 3 -4	3 4 5 -4
4 -1 2 3 4	-1 4 5 6
4 0 2 3 4	2 4 5 6
4 1 2 2 4	4 1 2 2 4

Решение

Вводим число [latex]n[/latex]. Используем цикл for и вводим число [latex]a[/latex]. Выводим неотрицательное число [latex]a[/latex], либо без изменений, либо увеличенное на два.
e-olymp.com
ideone.com

Ю 3.32

02/09/2016 by Рыжков Саша

Задача:
Вычислить [latex]x=2\left(\sin x-\frac{\sin 2x}{2}+\frac{\sin 3x}{3}-\cdots+\left(-1 \right)^{n-1} \frac{\sin nx}{n}\right), [/latex] [latex]-\pi < x < \pi [/latex]

Тесты

n	x	Сумма	Комментарий
3	1	0.867725	Пройден
2	2	2.575397	Пройден
1	5	-1.917849	Пройден

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in); 
		int n;
		double x;
		n = sc.nextInt();
		x = sc.nextInt();	       
		double result=0;
		int j = 1;
		for(int i = n; i > 0; i--){
			result += j * Math.sin(i * x) / i;
			j *= -1;
		}
		System.out.println(result);
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

Scanner sc = new Scanner(System.in);

int n;

double x;

n = sc.nextInt();

x = sc.nextInt();

double result=0;

int j = 1;

for(int i = n; i > 0; i--){

result += j * Math.sin(i * x) / i;

j *= -1;

}

System.out.println(result);

}

Описание решения:

Запишем общий вид суммы: [latex]2\sum_{i=1}^{n}{\left(-1 \right)^{n-1}}\frac{\sin ix}{i}[/latex]

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

Ссылка на ideone

e-olymp 1210. Очень просто!!!

24/08/2016 by Рыжков Саша

Задача.
Даны значения чисел [latex]n ,[/latex] [latex] a .[/latex]Вычислить $\sum_{i=1}^{n}i\cdot a^{i}$ !!!!!!!!!!!!!!!!!!!!!!!!!!!

Тесты

Ввод:	3 2	6 4	10 2
Вывод:	36	504	1100

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone{
        public static void main (String[] args) throws java.lang.Exception{
	float n,a;
        float sum = 0;
        Scanner sc = new Scanner(System.in);
        sc.useLocale(Locale.US);
        while (sc.hasNextFloat()){
            n = sc.nextFloat();
            a = sc.nextFloat();
            sum = n * a;
            for (int i = 1; i < n; i++){
                sum = sum * a;
            }
            System.out.println(sum);
        }
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone{

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

float n,a;

float sum = 0;

Scanner sc = new Scanner(System.in);

sc.useLocale(Locale.US);

while (sc.hasNextFloat()){

n = sc.nextFloat();

a = sc.nextFloat();

sum = n * a;

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

sum = sum * a;

}

System.out.println(sum);

}

Вводим два числа [latex]n[/latex],[latex]a[/latex] и [latex]sum[/latex] . Задаем цикл и суммируем до тех пор, пока [latex] i [/latex]не будет равно значению [latex]n[/latex].

Ссылка на ideone

e-olymp 931 Отношение произведения к сумме

07/07/2016 by Сережа Туромша

Задача:

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

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

Натуральное число [latex]n[/latex], не превышающее 2·10⁹.

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

Вывести отношение произведения цифр числа [latex]n[/latex] к их сумме с 3 десятичными цифрами.

Тесты:

Входные данные	Выходные данные
12345	8.000
5043	0.000
45	2.222

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

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 n, summ = 0, mult = 1;
		double ratio;
		n = x.nextInt();
		while(n != 0 && n) {
			summ += n % 10;
			mult *= n % 10;
			n /= 10;
		}
		ratio = (double)mult/summ;
		System.out.printf("%.3f", ratio);
	}
}

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 n, summ = 0, mult = 1;

double ratio;

n = x.nextInt();

while(n != 0 && n) {

summ += n % 10;

mult *= n % 10;

n /= 10;

}

ratio = (double)mult/summ;

System.out.printf("%.3f", ratio);

}

Алгоритм:
Для решения поставленной задачи нам нужно выделить отдельные цифры в записи данного числа, чтобы сосчитать их произведение и сумму. Воспользуемся циклом while. С помощью остатка от деления числа на 10 получаем последнюю цифру текущего числа, затем делим это число на 10. Получившиеся значения произведения и суммы цифр данного числа разделим, предварительно воспользовавшись явным преобразованием к типу [latex]double[/latex], и присвоим получившееся значение переменной ratio. Ответ с тремя десятичными цифрами после точки выводим с помощью метода [latex]printf[/latex]

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

Решение на e-olymp.com

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

e-olymp 109. Numeration

05/07/2016 by Владислав Козачков

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

Условие

Для нумерации $M$ страниц книги использовали $N$ цифр. По заданному $N$ вывести $M$ или $0$ , если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число $N$ . В книге не более $1001$ страницы.

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

Искомое количество страниц.

Тесты :

N	8	21	22	113	999	1001
M	8	15	0	61	369	0

Код на Java:

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

class Main {
	public static void main (String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = 1;
		while (true) {
			if (m < 10) {	//1 digit
				n -= 1;
			} else if (m < 100) {	//2 digits
				n -= 2;
			} else if (m < 1000) {	//3 digits
				n -= 3;
			} else {	//4 digits
				n -= 4;
			}
			if (n < 0) {
				m = 0;
			}
			if (n <= 0) {
				break;
			}
			m++;
		}
		System.out.print(m);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

int m = 1;

while (true) {

if (m < 10) { //1 digit

n -= 1;

} else if (m < 100) { //2 digits

n -= 2;

} else if (m < 1000) { //3 digits

n -= 3;

} else { //4 digits

n -= 4;

}

if (n < 0) {

m = 0;

}

if (n <= 0) {

break;

}

m++;

}

System.out.print(m);

}

Ход решения:

Принимаем исходное количество страниц $M$ как 1.
В зависимости от $M$ , вычитаем необходимое количество цифр из $N$ :

if (m < 10) {	//1 digit
	n -= 1;
} else if (m < 100) {	//2 digits
	n -= 2;
} else if (m < 1000) {	//3 digits
	n -= 3;
} else {	//4 digits
	n -= 4;
}

if (m < 10) { //1 digit

n -= 1;

} else if (m < 100) { //2 digits

n -= 2;

} else if (m < 1000) { //3 digits

n -= 3;

} else { //4 digits

n -= 4;

}

Далее проверяем условие выхода. Если при этом мы получили отрицательное значение $N$ , значит, исходное его значение также было неверным, тогда количеству страниц присваиваем 0:

if (n < 0) {
	m = 0;
}
if (n <= 0) {
	break;
}

if (n < 0) {

m = 0;

}

if (n <= 0) {

break;

}

Выйдя из цикла, выводим $M$ :

System.out.print(m);

28	System.out.print(m);

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com