- •Конспект лекций (часть 1) Оглавление
- •Введение
- •1. Этапы и проблемы решения задач с использованием компьютера
- •Алфавит языка
- •Ключевые слова
- •Идентификаторы
- •Знаки операций
- •Константы
- •Комментарии
- •2.3. Структура и основные элементы программы
- •2.4. Трансляция программ и их выполнение
- •3. Стандартные (базовые) типы данных, операции и выражения
- •3.1. Типы данных, переменные и константы Понятие типов данных
- •Классификация простых предопределенных типов данных
- •Переменные, константы
- •3.2. Целочисленные типы данных
- •3.3. Вещественные типы данных
- •3.4. Логический тип данных
- •3.5. Символьный тип данных
- •3.6. Операции и выражения
- •Преобразования типов данных
- •Операция присваивания
- •Арифметические операции
- •Операции отношения
- •Логические операции
- •Поразрядные (битовые) операции
- •Операции составного присваивания
- •Условная операция
- •Операция sizeof
- •Приоритеты рассмотренных операций
- •3.7. Ввод и вывод простых типов данных
- •Вывод текстовых строк
- •Ввод/вывод арифметических типов данных
- •Форматирование ввода / вывода
- •4.1. Идеи структурного программирования
- •Условная инструкция (if)
- •Инструкция множественного выбора (switch)
- •Цикл с предусловием (while)
- •Цикл с постусловием (do while)
- •Итерационный цикл (for)
- •Инструкции перехода
- •5. Приемы программирования циклов
- •5.1. Рекуррентные вычисления
- •5.2. Инвариант цикла
- •6. Массивы и указатели
- •6.1. Понятие массива
- •6.2. Объявление массивов Объявление одномерных массивов
- •Объявление многомерных массивов
- •6.3. Ввод-вывод массивов
- •6.4. Текстовые строки как массивы символов
- •6.5. Массивы и указатели
- •7. Разработка программ при работе с массивами
- •8. Функции и структура программы
- •9. Организация ввода/вывода и работа с файлами
- •Быстрое возведение чисел в целую степень
- •Нахождение наибольшего общего делителя (алгоритм Евклида)
Быстрое возведение чисел в целую степень
// ЦелаяСтепень.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
double IntPow(double b, int k, int &Count)
{
// Инвариант: (b ^ k) * p = a ^ n
// Цикл заканчивается при k = 0, тогда p = a ^ n
double p = 1;
Count = 0;
while (k != 0)
{
if (k & 1) // k не четно
{
-- k; // k = k - 1
p *= b; // p = p * b
}
else
{
k /= 2; // k = k / 2
b *= b; // b = b * b
}
++ Count;
}
return p;
}
double IntPow1(double a, int n, int &Count)
{
double p = 1;
double b = a;
for (int i = n, Count = 0; i; (i % 2) ? (p *= b, --i) : (b *= b, i /= 2),
++ Count);
return p;
}
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(0, "");
cout << " Алгоритм быстрого возведения числа в целую степень.\n";
cout << " ---------------------------------------------------\n";
for (char b = '1'; b != 27; cout << "\n\t\t\tПродолжим? (нет - Esc) ",
b = _getch(), cout << endl)
{
double a;
int n, N;
cout << "\nОснование степени: ";
cin >> a;
cout << "Целая степень: ";
cin >> n;
cout << '\n' << a << " в степени " << n << " равно " << fixed
<< IntPow(a, n, N) << ".\n";
cout << "Количество шагов: " << N << endl;
cout << '\n' << a << " в степени " << n << " равно " << fixed
<< IntPow1(a, n, N) << ".\n";
cout << "Количество шагов: " << N << endl;
}
return 0;
}
Нахождение наибольшего общего делителя (алгоритм Евклида)
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
int NOD_1(int n, int m, int &Count)
// Известно, что: НОД(n, m) = НОД(n - m, m) при n > m и
// НОД(n, m) = НОД(n, m - n) при n < m.
{
int r, a = n, b = m;
Count = 0;
// Инвариант: НОД(a, b) = НОД(n, m)
// Цикл заканчивается при a = b, тогда НОД(n, m) = НОД(a, a) = a
while (a != b)
{
if (a > b)
a = a - b;
else
b = b - a;
++ Count;
}
return a;
}
int NOD_2(int n, int m, int &Count)
// Известно, что: НОД(n, m) = НОД(m, r), где r - остаток от деления n на m.
{
int r, a = n, b = m;
Count = 0;
// Инвариант: НОД(a, b) = НОД(n, m)
// Цикл заканчивается при b = 0, тогда НОД(n, m) = НОД(a, 0) = a
while (b)
{
r = a % b;
a = b;
b = r;
++ Count;
}
return a;
}
int _tmain(int argc, _TCHAR* argv[])
{
setlocale(0, "");
cout << " Алгоритм Евклида для нахождения наибольшего общего делителя.\n";
cout << " ------------------------------------------------------------\n";
for (char b = '1'; b != 27; cout << "\n\t\t\tПродолжим? (нет - Esc) ",
b = _getch(), cout << endl)
{
int Count;
int n, m;
cout << "\n Введите два целых числа больших 0: ";
cin >> n >> m;
cout << "\n Значение НОД чисел " << n << " и " << m << " равно "
<< NOD_1 (n, m, Count) << endl;
cout << "Число итераций: " << Count << endl;
cout << "\n Значение НОД чисел " << n << " и " << m << " равно "
<< NOD_2 (n, m, Count) << endl;
cout << "Число итераций: " << Count << endl;
}
return 0;
}