Как составить программу по арифметике

Напишите программу, запрашивающую Ваше имя, Ваш возраст и рост в см (ввод с клавиатуры) и выводящую на экран следующее сообщение:
Здравствуйте, …
Вам … лет
Ваш рост … см

текст программы

Задача (урок )

Программа демонстрирующая работу функций div и mod.

Задача  (урок )
Напишите программу для вычисления значение выражения  

где x целое число, вводимое с клавиатуры.
Пояснение.
В данной задаче используется условный оператор if для того, чтобы исключить деление на 0. Пример алгоритма с ветвлением (или разветвляющийся алгоритм).

блок-схема
текст программы:
var x:integer;
    y:real;
begin
writeln(‘введите целое число’);
readln(x);
if (x-3)<>0 then
begin
  y:=(x+5)/(x-3);
  writeln (‘при x=’,x,’ y =’,y);
end
else
writeln(‘значение выражения не определено’);
end.

Задача (урок )

блок-схема вариант 1

Задача (урок )

Составить программу, которая если вводимое с клавиатуры целое число четное выводить на экран сообщение “это четное число”,  в противном случае – “это нечетное число”.

текст программы:
var x:integer;
begin
writeln(‘Ведите целое число’);
readln(x);
if x mod 2=0 then writeln(‘это четное число‘)
else writeln(‘это нечетное число‘);
end.

Задача (урок )

Составить программу, которая если вводимое с клавиатуры целое число больше 0 выводить на экран сообщение “это число положительное”, если число равно 0 – “это ноль”, если число меньше 0 – “это число отрицательное”.
var x:integer;
begin
writeln(‘Ведите целое число’);
readln(x);
if x>0 then writeln(‘это число положительное‘);
if x=0 then writeln(‘это ноль‘);
if x<0 then writeln(‘это число отрицательное‘);
end;

Задача (урок )
Составить программу-тест по арифметике, состоящую из 5 примеров. Программа должна работать следующим образом: на экран выводится пример (вопрос) и пользователь вводит ответ с клавиатуры. За 5 правильных ответов ставиться оценка “5”, за 4 – “4”, за 3 – “3”, за 2, 1, 0 правильных ответов оценка “2”.
Пояснение. 
При написании программы по данной задаче нам потребуется 5 переменных числового типа (лучше использовать тип real, но если оговорить, что ответами на примеры должны быть целые числа, ведь примеры подбирает сам учащийся, то используем тип integer). Назовем наши переменные для хранения ответов ot1, ot2, ot3, ot4, ot5, для оценки – oz. 
Подсчет и выставление оценки: через оператор if за каждый правильный ответ будем прибавлять 1 бал, а чтобы баллы накапливались используем формулу oz:=oz+1. Таким образом, в переменной oz будет храниться правильное количество ответов, но оценки 0 и 1 нет по условию задачи, следовательно нужно через if поставить “2” если oz<=2.

текст программы
var ot1,ot2,ot3,ot4,ot5:real;
    oz:integer;
begin
writeln(‘Вычислите’);

writeln(’12-4=?’);
readln(ot1);
if ot1=8 then oz:=oz+1;

writeln(‘3*15=?’);
readln(ot2);
if ot2=45 then oz:=oz+1;

writeln(‘8+13=?’);
readln(ot3);
if ot3=21 then oz:=oz+1;

writeln(‘7/2=?’);
readln(ot4);
if ot4=3.5 then oz:=oz+1;

writeln(‘9*7=?’);
readln(ot5);
if ot5=63 then oz:=oz+1;

if oz<=2 then oz:=2;
writeln(‘Ваша оценка ‘,oz); 
end.

Задача (урок )

Напишите программу для нахождения корней квадратного уравнения
текст программы
var a,b,c,D:integer;
    x1,x2:real;
begin
writeln(‘Решение квадратного уравнения a*x*x+b*x+c=0’);
writeln(‘введите a’);
readln(a);
writeln(‘введите b’);
readln(b);
writeln(‘введите c’);
readln(c);  
D:=b*b-4*a*c;
if D>=0 then
begin
x1:=(-b+sqrt(D))/2*a;
x2:=(-b-sqrt(D))/2*a;
writeln(‘x1=’,x1,’ x2=’,x2);
end
else writeln(‘нет корней’);
end.

Задача (урок )
Напишите программу нахождения наибольшего числа из трех случайных чисел от 1 до 10.
Для нахождения наибольшего числа из трех, нужно сначала сравнить два числа и выбрать наибольшее из них через оператор if, затем сравнить полученное наибольшее с третьим числом, если третье число больше, то переприсваиваем.

текст программы
var a,b,c,max:integer;
begin
a:=random(20)+1;
writeln(a);
b:=random(20)+1;
writeln(b);
c:=random(20)+1;
writeln(c);
readln(c);
if a>b then max:=a else max:=b;
if max<c then max:=c;
writeln (‘наибольшее из трех чисел ‘,max);
end.

Задача (урок )
Составьте программу, которая из 10 случайных чисел из промежутка от 10 до 20 находит количество чисел меньших 17. Оформите вывод следующим образом: вывод чисел через пробел в строчку, на следующей строке количество чисел меньших 17.
блок-схема
текст программы
var i,x,k:integer;
begin
k:=0;
for i:=1 to 10 do
begin
x:=random(11)+10;
write(x,’ ‘);
if x<17 then k:=k+1;
end;
writeln;
writeln(‘Количество меньших 17 ‘,k);
end.

Задача (урок )
Составьте программу, которая выводит на экран в строчку 15 случайных чисел из промежутка от 1 до 30 и подсчитывает количество четных чисел.
Пояснение. 
Обратите внимание, что переменная k – счетчик, поэтому начальное значение переменной обнуляем. Условие для подсчета четных: if a mod 2 =0 then k:=k+1, т.е. если  число четное, то k увеличивается на 1.
Текст программы
var i,a,k:integer;
begin
k:=0;
for i:=1 to 15 do
begin
a:=random(30)+1;
if a mod 2=0 then k:=k+1;
write(a,’ ‘);
end;
writeln;
writeln(‘Количество четных ‘,k);
end.

Задачи из ОГЭ по информатике на циклы:

Что будет напечатано в результате работы следующей программы?

var s,k:integer;

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

Где пишем?

Ничего на компьютер устанавливать не потребуется. Вполне достаточно прейти на сайт и найти там кнопочку “Начни создавать”. Не будем ставить себе цель еще и английский за одно подучить, так что установим на сайте русский язык.

Опыт показывает, что к играм, написанным самостоятельно, люди оказываются очень лояльны, так что можно себе позволить на первый раз сделать очень простой сюжет (иначе мы закопаемся и совсем ничего не сделаем): по сцене бежит мышка, а ее пытается догнать кошка, но мышь бежит постоянно, а кошке, чтобы сделать прыжок, надо решить пример. Если коту удается догнать мышь, то победа наша.

Готовим участников и декорации.

В нижней правой части экрана находятся две синие кнопки. Правая нужна для добавления в игру заднего фона, а левая – для добавления героев. Нажмем на правую, в выпадающем списке находим и нажимаем лупу и ищем понравившуюся декорацию. В Scratch это называется сценой и я предлагаю сегодня выбрать сцену в виде театральной сцены, вдруг ребенок так лучше терминологию запомнит?

Первый герой игры – это кот, он уже создан, теперь добавим второго – мышь. В Scratch всё, что способно двигаться по экрану, называется спрайт.

Видим, что мышь добавилась прямо на кота, не беда, по местам их можно расставить прямо мышкой (компьютерной, зажимает левую кнопку и тащим).

Начинаем делать анимацию. Движение мыши.

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

В левой части экрана расположены доступные операторы (команды), находим среди них “идти 10 шагов” в блоке “движение” и перетаскиваем в удобное место белого поля.

Если теперь нажать на эту синюю надпись, то мышь сдвинется. Покажите это ребенку! Обратите внимание на то, что число 10 написано на белом фоне, значит вместо него можно написать другое число или переменную. Попробуйте написать вместо 10 единицу или 40, посмотрите что изменится.

Но нам, конечно, хочется, чтобы мышь двигалась без нашего участия. Нет ничего сложного в том, чтоб это организовать. Надо только сказать программе когда выполнять команду. В нашем случае всегда, так что находим в блоке “Управление” команду “повторять всегда”. Внутри этой оранжевой “детальки” есть место для других команд, причем добавить их можно туда сколько угодно, хотя кажется, что место там есть только для одной. Помещаем туда нашу “идти 10 шагов”, и, чтобы мышь не бежала слишком быстро, добавим еще “ждать 1 секунд”. Если сейчас нажать на блок команд, то мышь будет двигаться до тех пор, пока от нее не останется виден один хвостик. Не хочется каждый раз за этот хвостик ее вытаскивать из-за кулис, вместо этого добавим в программу еще одну команду: “установить x в -40”, выполняться она должна не на каждом шаге, а при запуске программы, так что расположить эту команду надо перед блоком “повторять всегда”.

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

Сделаем так, чтобы программа запускалась по нажатию флажка, расположенного над сценой. Для этого есть специальный оператор “когда флаг нажат”, помещаем эту команду выше всех остальных.

Длину шагов и их частоту можно варьировать по своему усмотрению, пока предлагаю установить “идти 3 шагов”, “ждать 0.5 секунд”.

Мультик про мышь готов! Можно его запустить и посмотреть на полном экране.

Основная часть программы. Вопросы и шаги кота.

Нажмем на спрайт кота в правой нижней четверти экрана и убедимся, что перед нами открылся чистый лист с изображением кота в правом верхнем углу. Сразу начнем программу с оператора “когда флаг нажат”, добавим “установить x в -140” и (пока еще пустой) блок “повторять всегда”.

Теперь момент сложный для того, кто не занимался программированием. Надо понять, что если мы хотим пользоваться в программе какими-то данными, то эти данные приходится где-то хранить и уметь к ним обращаться. Для этого придумали переменные – что-то вроде ника/клички/погоняла наших данных. Возьмет наша программа число 5, назовет его “число_1” и везде вместо “5” может использовать “число_1”. Кажется, что это очень неудобно, но это только кажется, потому что значение в “число_1” можно задавать автоматически, а вот “5” придется набирать каждый раз вручную. Набираемся немного терпения и разбираемся на примере.

Для начала переменные надо создать, для этого прокручиваем список команд почти до самого конца находим там и нажимаем белую кнопочку “Создать переменную”, в появившемся окне задаем имя “число_1”. Нам потребуется две переменных, так что аналогично делаем для “число_2”.

Чуть ниже списка переменных находим команду “задать моя переменная значение 0”, дважды перетаскиваем этот оператор на поле ввода кода. В выпадающем списке первого выберем “число_1”, а второго “число_2”.

А записывать в переменную мы будем случайное число, Scratch нам это позволяет. В группе “Операторы” находим “выдать случайное от 1 до 10”.

Мне сейчас хочется, чтобы мои дети немного привыкали умножать за пределами таблицы Пифагора, поэтому число_1 задам не до 10, а до 20, а вы можете делать по своему усмотрению, хоть оба числа от 0 до 2, хоть оба трехзначных, только не перегните палку, если на решение примера ребенок будет тратить по 2 минуты, то вряд ли ему понравится игра.

Числа готовы, надо чтобы программа научилась задавать примеры. Тут будет еще один непривычный далекому от программирования человеку момент, чтобы что-то вывести на экран, надо сначала сделать из этого строку. Получившуюся строку мы вложим в уста кота. Я не буду словами описывать используемые операторы, предлагаю посмотреть фото. Прокомментирую только заполнение окошек. В первое переносим из области операторов нашу переменную число_1, во второе пишем знак умножения (если хотим точку в середине строки, то зажимает на клавиатуре ALT, убеждаемся, что нажат NumLock, набираем на дополнительной клавиатуре число 250, отпускаем ALT), в третьем окошке переменная число_2, а в четвертом – знак вопроса. А еще – будьте аккуратны когда добавляете один оператор в первое окошко второго, смотрите, чтобы при этом выделялось только первое окошко, а не два сразу и только тогда отпускайте левую кнопку мыши.

После того как вопрос задан, пользователь введет на него ответ. Если ответ правильный, то кот должен сделать шаг вперед. Там, где действия программы зависят от каких-то условий, используются условные операторы. Находим блок “если то”, вставляем в шестиугольник между его словами зеленый шестиугольник “__= 50”, в первое окошко этого зеленого оператора перетягиваем из области команд голубой овал с надписью “ответ”, а вместо числа “50” овальный зеленый оператор умножения, а уже в него – оранжевые овалы с именами наших переменных.

А в белый зазор нам надо поместить список действий, которые поручено выполнять коту, если ответ окажется правильным. Ну, это мы уже делали с мышью: “идти 10 шагов” и “следующий костюм” помещаем друг за другом.

Собираем все блоки в одну программу и получаем

Теперь основная часть программы готова, можно дать ее “настроить” ребенку. Ну, скорости движения подправить, например, чтоб кот мышку догнать мог, но не слишком быстро. Можно разрешить поиграться с размерами героев, их меняют на панели под изображением сцены. Главное, когда ребенок все это будет делать, ему придется решать примеры, причем добровольно, а как надоест, он сам остановится.

Завершение работы программы, определение победителя

Осталось совсем чуть-чуть. Если кот догнал мышь, то он победил. Конечно, снова потребуется условный оператор “если то”. На это раз в шестиугольник между “если” и “то” надо добавить оператор голубого цвета “касается указатель мыши ?” и вместо “указатель мыши” выбираем “Mouse1”.

А что делать, если условие выполниться? Сообщить о победе! Можно оформить ее сообщением кота, а можно сделать чуть более яркой. Напишу про второй вариант.

В правой нижней четверти экрана нажимаем на панель “Сцена”. В левом верхнем углу открываем вкладу “Фоны”. Кликаем правой кнопкой мыши на “Theater” и в выпадающем меню выбираем “Дублировать”. Кликаем мышью на созданный только что “Theater2” и добавляем на него текст “Победа” с помощью соответствующей кнопки, находящейся на панели в центральной части экрана. Аналогично делаем фон “Theater3” с надписью “Увы! Не в этот раз”.

Возвращаемся на вкладку “Код”, выбираем спрайт кота и велим ему в случае победы “переключить фон на Theater2” и остановить выполнение скриптов с помощью оператора “стоп все”. А в самое начало программы добавим “переключить фон на Theater”.

А в каком случае мы будем считаться проигравшими? (кстати, а надо ли? Может быть вашему ребенку больше понравится играть, если проиграть невозможно?) Предлагаю объявить поражение в том случае, если мышь успеет уйти со сцены. Возвращаемся в код, который мы писали для Mouse1 и добавим ей проверку на столкновение с концом сцены. В знакомый нам “если то” вставляем условие “касается указатель мыши?”, заменив в нем “указатель мыши” на “край”, а в белый зазор “переключить фон на Theater3” и “стоп все“.

Вот такая игра получилась, не забудьте ее сохранить, для этого выберите “Файл” – “Сохранить на свой компьютер”

Ссылка на готовый проект.

Ну и, как я обещала вначале статьи, добавляю ссылку на готовый проект, его можно редактировать по своему усмотрению или играть в том виде, в котором он есть.

Буду рада любой обратной связи и замечаниям по содержанию, подаче материала, количеству и качеству иллюстраций. Возможно, это статья окажется не последней на тему создания игр в Scratch.

Время на прочтение
8 мин

Количество просмотров 76K

В большинстве современных языков программисту уже не нужно заботиться о числах, с которыми процессор непосредственно манипулировать не может. Где-то, как в Python или Haskell, поддержка длинных целочисленных типов встроена прямо в ядро языка, где-то, как в Java или C#, реализована в виде отдельных классов. Но в стандартной библиотеке языка C++ длинные числа до сих пор не поддерживаются. Поэтому я решил написать её сам.

Структура класса

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

class big_integer {
	// основание системы счисления (1 000 000 000)
	static const int BASE = 1000000000;

	// внутреннее хранилище числа
	std::vector<int> _digits;

	// знак числа
	bool _is_negative;
};

В моей реализации будет сразу два представления нуля — в виде пустого вектора и в виде вектора с одним-единственным нулём.

Создание числа

Первое, что нужно научиться делать — это создавать число. Вот так оно преобразуется из строки, содержащей цифры:

big_integer::big_integer(std::string str) {
        if (str.length() == 0) {
                // из пустой строки создается ноль
                this->_is_negative = false;
        }
        else {
                if (str[0] == '-') {
                        str = str.substr(1);
                        this->_is_negative = true;
                }
                else {
                        this->_is_negative = false;
                }
                // Вообще-то i должно иметь тип size_t. Но так как это беззнаковый тип,
                // а в int размер теоретически может и не влезть, я использовал long long
                for (long long i = str.length(); i > 0; i -= 9) {
                        if (i < 9)
                                this->_digits.push_back(atoi(str.substr(0, i).c_str()));
                        else
                                this->_digits.push_back(atoi(str.substr(i - 9, 9).c_str()));
                }
                // удалим из числа ведущие нули, если они есть
                this->_remove_leading_zeros();
        }
}

Код процедуры удаления ведущих нулей прост до безобразия:

void big_integer::_remove_leading_zeros() {
        while (this->_digits.size() > 1 && this->_digits.back() == 0) {
                this->_digits.pop_back();
        }
        // этот код нужен, чтобы у нас не было отрицательного нуля
        if (this->_digits.size() == 1 && this->_digits[0] == 0) this->_is_negative = false;
}

Также нам нужно уметь преобразовывать обычные числа в длинные:

big_integer::big_integer(signed long long l) {
        if (l < 0) { this->_is_negative = true; l = -l; }
        else this->_is_negative = false;
        do {
                this->_digits.push_back(l % big_integer::BASE);
                l /= big_integer::BASE;
        } while (l != 0);
}
 
big_integer::big_integer(unsigned long long l) {
        this->_is_negative = false;
        do {
                this->_digits.push_back(l % big_integer::BASE);
                l /= big_integer::BASE;
        } while (l != 0);
}

Код преобразования из остальных типов еще проще, я не стал приводить его здесь.

Вывод числа

Теперь нам нужно научиться печатать наше число в поток и преобразовывать его в строку:

std::ostream& operator <<(std::ostream& os, const big_integer& bi) {
        if (bi._digits.empty()) os << 0;
        else {
                if (bi._is_negative) os << '-';
                os << bi._digits.back();
                // следующие числа нам нужно печатать группами по 9 цифр
                // поэтому сохраним текущий символ-заполнитель, а потом восстановим его
                char old_fill = os.fill('0');
                for (long long i = static_cast<long long>(bi._digits.size()) - 2; i >= 0; --i) {
                        os << std::setw(9) << bi._digits[i];
                }

                os.fill(old_fill);
        }
 
        return os;
}

big_integer::operator std::string() const {
        std::stringstream ss;
        ss << *this;
        return ss.str();
}

Сравнение чисел

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

bool operator ==(const big_integer& left, const big_integer& right) {
        // числа разных знаков точно не равны
        if (left._is_negative != right._is_negative) return false;
        // поскольку у нас два представления нуля, нужно это особо обработать
        if (left._digits.empty()) {
                if (right._digits.empty() || (right._digits.size() == 1 && right._digits[0] == 0)) return true;
                else return false;
        }

        if (right._digits.empty()) {
                if (left._digits.size() == 1 && left._digits[0] == 0) return true;
                else return false;
        }
        // так как у нас нет ведущих нулей, то в числах должно быть одинаковое количество цифр (разрядов)
        if (left._digits.size() != right._digits.size()) return false;
        for (size_t i = 0; i < left._digits.size(); ++i) if (left._digits[i] != right._digits[i]) return false;
 
        return true;
}

Теперь проверим, меньше ли одно число другого:

bool operator <(const big_integer& left, const big_integer& right) {
        if (left == right) return false;
        if (left._is_negative) {
                if (right._is_negative) return ((-right) < (-left));
                else return true;
        }
        else if (right._is_negative) return false;
        else {
                if (left._digits.size() != right._digits.size()) {
                        return left._digits.size() < right._digits.size();
                }
                else {
                        for (long long i = left._digits.size() - 1; i >= 0; --i) {
                                if (left._digits[i] != right._digits[i]) return left._digits[i] < right._digits[i];
                        }
                       
                        return false;
                }
        }
}

Здесь мы используем унарное отрицание, чтобы сменить знак числа. Также я для симметрии ввел унарный плюс:

const big_integer big_integer::operator +() const {
        return big_integer(*this);
}
 
const big_integer big_integer::operator -() const {
        big_integer copy(*this);
        copy._is_negative = !copy._is_negative;
        return copy;
}

Знания о том, почему нужно возвращать const big_integer, а не просто big_integer, а также о правилах выбора между дружественной функцией-оператором и оператором-членом класса, я подчерпнул из этой статьи.

Дальше все совсем просто:

bool operator !=(const big_integer& left, const big_integer& right) {
        return !(left == right);
}
 
bool operator <=(const big_integer& left, const big_integer& right) {
        return (left < right || left == right);
}
 
bool operator >(const big_integer& left, const big_integer& right) {
        return !(left <= right);
}
 
bool operator >=(const big_integer& left, const big_integer& right) {
        return !(left < right);
}

Арифметические операции

Сложение

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

const big_integer operator +(big_integer left, const big_integer& right) {
        // мы напишем лишь сложение двух положительных чисел
        // остальное мы выведем, используя смену знака и вычитание
        if (left._is_negative) {
                if (right._is_negative) return -(-left + (-right));
                else return right - (-left);
        }
        else if (right._is_negative) return left - (-right);
        int carry = 0; // флаг переноса из предыдущего разряда
        for (size_t i = 0; i < std::max(left._digits.size(), right._digits.size()) || carry != 0; ++i) {
                if (i == left._digits.size()) left._digits.push_back(0);
                left._digits[i] += carry + (i < right._digits.size() ? right._digits[i] : 0);
                carry = left._digits[i] >= big_integer::BASE;
                if (carry != 0) left._digits[i] -= big_integer::BASE;
        }
 
        return left;
}

Здесь я избежал «дорогой» операции деления в случае, когда получившаяся «цифра» больше основания, по которому я работаю, путем простого сравнения.

Вычитание

В принципе, вычитание аналогично сложению. Нужно лишь рассмотреть случай, когда уменьшаемое меньше вычитаемого:

const big_integer operator -(big_integer left, const big_integer& right) {
        if (right._is_negative) return left + (-right);
        else if (left._is_negative) return -(-left + right);
        else if (left < right) return -(right - left);
        int carry = 0;
        for (size_t i = 0; i < right._digits.size() || carry != 0; ++i) {
                left._digits[i] -= carry + (i < right._digits.size() ? right._digits[i] : 0);
                carry = left._digits[i] < 0;
                if (carry != 0) left._digits[i] += big_integer::BASE;
        }
 
        left._remove_leading_zeros();
        return left;
}

Инкремент и декремент

Перед реализацией этих двух операций нам нужно реализовать сложение и вычитание с присвоением:

big_integer& big_integer::operator +=(const big_integer& value) {
        return *this = (*this + value);
}

big_integer& big_integer::operator -=(const big_integer& value) {
        return *this = (*this - value);
}

Тогда префиксные версии операций реализуются в одну строчку, а постфиксные — лишь немногим сложнее:

const big_integer big_integer::operator++() {
        return (*this += 1);
}

const big_integer big_integer::operator ++(int) {
	*this += 1;
	return *this - 1;
}

const big_integer big_integer::operator --() {
	return *this -= 1;
}

const big_integer big_integer::operator --(int) {
	*this -= 1;
	return *this + 1;
}

Умножение

Я не стал писать быстрое умножение Карацубы, а снова использовал «школьную» арифметику:

const big_integer operator *(const big_integer& left, const big_integer& right) {
        big_integer result;
        result._digits.resize(left._digits.size() + right._digits.size());
        for (size_t i = 0; i < left._digits.size(); ++i) {
                int carry = 0;
                for (size_t j = 0; j < right._digits.size() || carry != 0; ++j) {
                        long long cur = result._digits[i + j] +
                                left._digits[i] * 1LL * (j < right._digits.size() ? right._digits[j] : 0) + carry;
                        result._digits[i + j] = static_cast<int>(cur % big_integer::BASE);
                        carry = static_cast<int>(cur / big_integer::BASE);
                }
        }
        // не забудем про знак
        result._is_negative = left._is_negative != right._is_negative;
        result._remove_leading_zeros();
        return result;
}

Деление

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

void big_integer::_shift_right() {
        if (this->_digits.size() == 0) {
                this->_digits.push_back(0);
                return;
        }
        this->_digits.push_back(this->_digits[this->_digits.size() - 1]);
        // здесь размер массива равен как минимум двум и перебор идет до предпоследнего разряда,
        // поэтому i имеет "верный" тип size_t
        for (size_t i = this->_digits.size() - 2; i > 0; --i) this->_digits[i] = this->_digits[i - 1];
        this->_digits[0] = 0;
}

Теперь опишем само деление:

const big_integer operator /(const big_integer& left, const big_integer& right) {
        // на ноль делить нельзя
        if (right == 0) throw big_integer::divide_by_zero();
        big_integer b = right;
        b._is_negative = false;
        big_integer result, current;
        result._digits.resize(left._digits.size());
        for (long long i = static_cast<long long>(left._digits.size()) - 1; i >= 0; --i) {
                current._shift_right();
                current._digits[0] = left._digits[i];
                current._remove_leading_zeros();
                int x = 0, l = 0, r = big_integer::BASE;
                while (l <= r) {
                        int m = (l + r) / 2;
                        big_integer t = b * m;
                        if (t <= current) {
                                x = m;
                                l = m + 1;
                        }
                        else r = m - 1;
                }
 
                result._digits[i] = x;
                current = current - b * x;
        }
 
        result._is_negative = left._is_negative != right._is_negative;
        result._remove_leading_zeros();
        return result;
}

Здесь big_integer::divide_by_zero это пустой класс, унаследованный от std::exception.

Взятие остатка

Вообще-то в предыдущей операции остаток фактически хранится в переменной current. Но я задался вопросом определения знака остатка. Википедия говорит, что остаток от деления всегда положителен. Поэтому я написал такую версию этой операции:

const big_integer operator %(const big_integer& left, const big_integer& right) {
        big_integer result = left - (left / right) * right;
        if (result._is_negative) result += right;
        return result;
}

Возведение в степень

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

bool big_integer::odd() const {
        if (this->_digits.size() == 0) return false;
        return this->_digits[0] & 1;
}

bool big_integer::even() const {
        return !this->odd();
}

Теперь напишем само возведение:

const big_integer big_integer::pow(big_integer n) const {
        big_integer a(*this), result(1);
        while (n != 0) {
                if (n.odd()) result *= a;
                a *= a;
                n /= 2;
        }
 
        return result;
}

Полный код класса: pastebin.com/MxQdP5s9

Всё! Теперь можно вычислить, к примеру, 2¹⁰⁰⁰, либо факториал 100:

#include <iostream>
#include "big_integer.hpp"
using namespace std;


int main() {
	big_integer bi("2"), bi2 = 100;
	cout << bi.pow(1000) << endl;
	big_integer f = 1;
	for (big_integer i = 2; i <= bi2; ++i) f *= i;
	cout << f << endl;
}

Литература

1. e-maxx.ru — сайт, посвященный олимпиадным алгоритмам
2. cppalgo.blogspot.ru/2010/05/blog-post.html — блог Игоря Беляева

Формулировка задачи:

Программа должна работать следующим образом. На метке выдается задание – арифметическое действие вида “23+41=”, где числа выбираются случайным образом в интервале 10-100. Ученик выбирает правильный ответ из 3 вариантов, щелкая мышкой на соответствующем переключателе (варианты ответов выводить, используя свойство caption переключателей). Если помечен флажок “подсчитывать очки”, то выводить на метке количество угаданных ответов. Предусмотреть возможность выбора учителем арифметического действия с использованием переключателей “+”,”-“,”*”,”/”, а также возможность изменения интервала используемых чисел при помощи линейки прокрутки. Число нажатий . Заранее спасибо)

Код к задаче: «Написать программу, тестирующую младшеклассников по арифметике»

textual

Private Sub Command1_Click()
Static n As Integer
n = n + 1
Label6.Caption = n
...

Задачи целочисленной арифметики

Пример:
Дано целое число. Определить, совпадают
ли первая и последняя цифра данного
целого числа

Решение
Последнюю цифру числа можно сразу
определить как остаток от деления
данного числа на 10. А вот первую мы будем
определять, последовательно отбрасывая
цифры путем деления на 10 до тех пор, пока
не останется одна цифра. Это и будет
первая цифра данного числа.

{последняя
цифра}

{тело цикла}

{условие выхода из цикла}

Var
N,R
: longint;

BEGIN

Write(‘Введите
целое число’); readln(
N);

R:= N
mod 10;

Repeat

N:=N div 10

Until N < 10;

If R=N then
writeln(‘совпадают’) else writeln(‘не совпадают’);

Readln;

END.

1. Подсчитать сумму
   и количество цифр данного натурального
   числа

2. Сообщить, есть ли
   в данном натуральном числе N
   цифра A.

3. Подсчитать количество нечетных
   натуральных чисел, принадлежащих
   интервалу ( a , b ),
   у которых количество четных цифр равно
   заданному числу.

4. Подсчитать количество чисел Фибоначчи,
   принадлежащих интервалу [ a , b ),
   в которых младшая цифра кратна заданной

5. Подсчитать
   количество четных натуральных чисел,
   принадлежащих интервалу [ a , b ),
   у которых количество четных цифр больше
   количества нечетных цифр

6. Подсчитать
   количество натуральных чисел,
   принадлежащих отрезку [ a , b ],
   в записи которых нечетные цифры
   отсутствуют^.

7. Подсчитать
   количество n-значных
   натуральных чисел, в которых сумма цифр
   нечетная, а младшая цифра – четная

8. Подсчитать
   количество двузначных и трехзначных
   натуральных чисел, в которых сумма цифр
   четная и кратна младшей цифре.

9. Определить, есть
   ли среди простых чисел из интервала
   [ a , b ),
   такие, в которых младшая цифра больше
   старшей цифры.

Структурное программирование. Подпрограммы.

Структурное
программирование подразумевает разбиение
большой задачи на отдельные, логически
законченные части и написание подпрограмм,
реализующих каждую
часть
задачи.
Каждая такая часть программы получает
свое имя. Тогда всю большую программу
мы можем написать, вызывая по именам
отдельные ее части в нужной нам
последовательности.

Для пояснения
вышесказанного проведем аналогию,
например, в кулинарии: Если мы собираемся
испечь торт “Наполеон”, мы возьмем
кулинарную книгу и посмотрим рецепт,
который гласит, что нужно приготовить
300 г. слоеного теста, испечь из него 6
Вычислить значение функции коржей.
Затем приготовить 200 г. заварного крема
и смазать им коржи. Эта сложная задача
имеет команды: приготовить
слоеное тесто
и приготовить
заварной крем.
В рецепте они подробно не описаны.
Видимо, мы откроем раздел, где описано
приготовление различного рода теста и
посмотрим, как приготовить слоеное
тесто. Затем в разделе “Кремы” посмотрим
как приготовить заварной крем. Очевидно,
что заварной крем может использоваться
и в других рецептах, например, для
изготовления заварных пирожных, возможно,
что лишь количество его будет другим.
Также и слоеное тесто. Очевидно, что
было бы просто нерационально каждый
раз, где потребуется в рецептах такой
крем, заново описывать его приготовление-
объем кулинарной книги неоправданно
бы возрос.

Возвращаясь к
программированию, можно сказать, что
структурированная задача имеет следующие
достоинства:

• легче читается-
  становится понятней

• легче отлаживается
  (отдельными подпрограммами)- сокращается
  вероятность ошибок

• одну и ту же
  подпрограмму можно вызывать в программе
  многократно. (сокращается объем текста
  программы)

• одну задачу могут
  разрабатывать несколько программистов
  одновременно (при не использовании
  глобальных величин)

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

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

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

procedure
<имя процедуры> [(список
формальных параметров)];
-{ заголовок

обязателен в
отличие от

заголовка программы}

<раздел описаний
> {здесь- описаны локальные величины}

Begin

<операторы>
{ исполняемая часть процедуры}

Еnd;

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

Процедура призвана
решить какую-то небольшую задачу. В
любой задаче есть результат решения,
который должен после отработки процедуры
быть сохранен в переменной. В задаче
могут быть исходные данные (переменные
или константы).

И исходные
данные и результат
должны быть занесены в список параметров
процедуры.
Параметры процедуры различаются:

Формальные

в описательной
части программы

следуют за
заголовком процедуры

п
еречислены
имена переменных с указанием типов

з
адают
шаблон для фактических

Фактические
параметры

в исполняемой
части программы

следуют за именем
процедуры

перечислены только
имена без указания типа

заполняют шаблон
конкретными значениями

Решим задачу с
использованием процедуры.

Пример Даны
длины сторон двух треугольников.
Определить, какой треугольник имеет
большую площадь.

Решение
Очевидно, что в данной задаче после
ввода исходных данных необходимо будет
дважды выполнять одни и те же действия:
вычислять площадь треугольника (по
Формуле Герона). Оформим данный алгоритм
в виде подпрограммы. Тогда можно будет
просто дважды вызвать эту подпрограмму
по имени, указав в качестве параметров
каждый раз длины сторон одного из
треугольников.

Var

S1,
S2:
real;
{площади двух треугольников}

a1,b1,c1,a2,b2,c2:
real; {величины сторон}

procedure
pl (a,b,c:real; var s:real);

var p:real;

begin

(p:=a+b+c)/2;

s:=sqrt(p*(p-a)*(p-b)*(p-c));

end;

BEGIN

Write(‘Введите
длины сторон первого треугольника
‘);readln(a1,b1,c1);

Write(‘Введите
длины сторон второго треугольника
‘);readln(a2,b2,c2);

Pl(a1,b1,c1,s1);

Pl(a2,b2,c2,s2);

If
s1>s2
then
writeln(‘площадь
первого треугольника больше’)

else

if
s2>s1
then
writeln(‘площадь
второго треугольника больше’)

else
writeln
(‘треугольники равновелики’);

END.

Использование
параметров делает подпрограмму
универсальной.
Именно использование параметров
позволило получить разный результат
работы одной и той же подпрограммы
(площадь) при разных исходных данных
(длины сторон). Исходные
данные подпрограммы передаются по
значению-параметры- значения
(в списке формальных параметров
указываются без слова var
перед именами переменных). Результат
работы процедуры передается по ссылке-
параметры-переменные
(в списке формальных параметров перед
именами переменных пишется слово var)

При вызове процедуры
в программе формальные параметры
заменяются фактическими, причем
параметры-значения
могут заменяться как переменными, так
и произвольными выражениями
(как частный случай числами), параметры-
переменные могут заменяться при вызове
только переменными соответствующего
типа.
Фактические
и формальные параметры должны совпадать
по количеству, порядку следования и
типу.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #

  07.06.2015135.34 Кб411.docx

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #