Арифметические задачи

Министерство Образования и Науки Российской Федерации                  Новосибирский Государственный Технический Университет

Лабораторная Работа №1

По дисциплине “Информатика”

Арифметические Задачи

НОВОСИБИРСК 2023

1

Задание

УДВОЕНИЕ ЧИСЛА

Некоторое натуральное число заканчивается на двойку. Если её переставить на первое место, то число удвоится. Какое минимальное число было изначально?

Следствия из условия задачи

“Некоторое натуральное число” - наше число лежит в промежутке от 0 до бесконечности,

“заканчивается на двойку” - число заканчивается на цифру 2, т.е. оно чётное.

“Если её переставить на первое место, то число удвоится” – если переставить двойку на первое место, то число удвоится, т.е. Переставить цифру 2 с конца в начало   =   умножить число на 2. В вербальном виде условие выглядит так

(N / 10) + (N % 10) * 10^k  = N * 2, где N- наше неизвестное число, k – степень нашего числа.

“Какое минимальное число было изначально?” – это вопрос, на который мы должны дать ответ, то есть найти число неизвестное число N, поставленное задание необходимо написать на языке программирования C.

Теоретический материал

 Натуральное число  числа, возникающие естественным образом при счёте, это числа 1, 2, 3, 4, 5, 6, 7 и так далее до бесконечности, последовательность всех натуральных чисел, расположенных в порядке возрастания, называется натуральным рядом, в котором есть наше неизвестное число N.

  Тип данных int: представляет целое число. Диапазон предельных значений соответственно варьируется от −2 147 483 648 до 2 147 483 647 (при 4 байтах).

2

  Забегая вперёд мы должны использовать, unsigned long int или unsigned long long int,  так как наше неизвестное число N, очень большое и следовательно нам понадобится соответствующие типы данных.

  Дополнительная Информация: Решая данную задачу, мы не использовали метода перебора, так как, во-первых на это уйдёт много времени и это решение будет не рациональным, во-вторых мы создали алгоритм, на основе условий и известных нам знаний, который вычисляет неизвестное нам число N, более надёжным и рациональным способом.

Проектирование программы

Обсуждение основных идей алгоритма

 Идея: При простом переборе, по заданному условию, уйдёт слишком много времени. Даже если перебирать все числа, у которых младший разряд «2», то есть 2, 12,22, 32 и т. д., то уйдёт слишком много времени, потому что сложность такого алгоритма будет О(n/10).

 Для более быстрого решения задачи был использован такой алгоритм:

 Представим наше число в виде: x[1]x[2]x[3]…x[n]; По  условию нам известно, что младший разряд исходного числа равен «2» => наше число можно представить в виде x[1]x[2]x[3]…2;

Получившееся число 2x[1]x[2]x[3]…x[n-1]; Получится оно должно  в результате умножения на 2 или переносе младшего  разряда (2) в старший. Отсюда можно сделать вывод, что разряд исходного числа перед «2» должен быть «4» (потому что 2*2=4), а перед этой «4» должна быть «8» и т. д.

Таким образом наименьшее число, соответствующее данному условию должно иметь вид x[1]x[2]x[3]…842  и каждое следующие число можно найти по формуле:

x[k]=((x[k-1]*2) mod 10)+((x[k-2]*2) div 10)

Таким образом, мы будем находить следующие числа до тех пор, пока не дойдём до следующей «2», после которой (по нашей формуле) будет идти 4, за ней, 8 и т. д. Для этого вторая часть формулы ((x[k-2]*2) div 10)) должна равняться нулю.

3

«Составные части» программы

• Подключаем необходимые библиотеки

#include<stdio.h>