2014-02-24
629
Быстрое возведение чисел в целую степень
// ЦелаяСтепень.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;
}
Предмет дисциплины и ее задачи. Содержание и форма проведения занятий. Связь с другими дисциплинами учебного плана.
