1:
int Degree(int a, int n)
{
int result = 1;
for(int i = 1; i<=n; i++)
result *= 1;
return result;
}
2:
int FastDegree(int a, int n)
{
int k = n;
int b = 1;
int c = a;
while(k!=0)
{
if(k%2==0)
{
k /= 2;
c *= c;
}
else
{
k--;
b *= c;
}
}
return b;
}
3:
int Mult(int a, int b)
{
int result = 0;
for(int i = 0; i!=b; i = i+1)
result = result+a;
return result;
}
4:
void Divmod(int a, int d, out int div, out int mod)
{
int sum = 0;
int i = 0;
while(true)
{
sum += d;
if(sum>a)
{
div = i;
mod = a+d-sum;;
return;
}
else if(sum==a)
{
div = i+1;
mod = 0;
return;
}
else
i++;
}
}
5:
void Fibonacci(int n)
{
if((n==0)||(n==1))
return 1;
int fi2 = 1;
int fi1 = 1;
int i = 2;
while(i<=n)
{
int t = fi2+fi1;
fi2 = fi1;
fi1 = t;
i++;
}
return fi1;
}
Перевести с Pascal на С#
1. Дано целое число а и натуральное (целое неотрица-
тельное) число n. Вычислить а в степени n. Другими словами, не-
обходимо составить программу, при исполнении которой значения
переменных а и n не меняются, а значение некоторой другой пере-
менной (например, b) становится равным а в степени n. (При этом
разрешается использовать и другие переменные.)
Решение. Введем целую переменную k, которая меняется от 0
до n, причем поддерживается такое свойство: b = (a в степени
k).
k := 0; b := 1;
{b = a в степени k}
while k <> n do begin
| k := k + 1;
| b := b * a;
end;
Другое решение той же задачи:
k := n; b := 1;
{a в степени n = b * (a в степени k)}
while k <> 0 do begin
| k := k - 1;
| b := b * a;
end;
2. Решить предыдущую задачу, если требуется, чтобы чис-
ло действий (выполняемых операторов присваивания) было порядка
log n (то есть не превосходило бы C*log n для некоторой констан-
ты C; log n - это степень, в которую нужно возвести 2, чтобы по-
лучить n).
Решение. Внесем некоторые изменения во второе из предложен-
ных решений предыдущей задачи:
k := n; b := 1; c:=a;
{a в степени n = b * (c в степени k)}
while k <> 0 do begin
| if k mod 2 = 0 then begin
| | k:= k div 2;
| | c:= c*c;
| end else begin
| | k := k - 1;
| | b := b * c;
| end;
end;
Каждый второй раз (не реже) будет выполняться первый вариант
оператора выбора (если k нечетно, то после вычитания единицы
становится четным), так что за два цикла величина k уменьшается
по крайней мере вдвое.
3. Даны натуральные числа а, b. Вычислить произведение
а*b, используя в программе лишь операции +, -, =, <>.
Решение.
var a, b, c, k : integer;
k := 0; c := 0;
{инвариант: c = a * k}
while k <> b do begin
| k := k + 1;
| c := c + a;
end;
{c = a * k и k = b, следовательно, c = a * b}
4. Дано натуральное (целое неотрицательное) число а и
целое положительное число d. Вычислить частное q и остаток r при
делении а на d, не используя операций div и mod.
Решение. Согласно определению, a = q * d + r, 0 <= r < d.
{a >= 0; d > 0}
r := a; q := 0;
{инвариант: a = q * d + r, 0 <= r}
while not (r < d) do begin
| {r >= d}
| r := r - d; {r >= 0}
| q := q + 1;
end;
5. Последовательность Фибоначчи определяется так:
a(0)= 1, a(1) = 1, a(k) = a(k-1) + a(k-2) при k >= 2. Дано n,
вычислить a(n).
6. Та же задача, если требуется, чтобы число операций
было пропорционально log n. (Переменные должны быть целочислен-
ными.)
Указание. Пара соседних чисел Фибоначчи получается из пре-
дыдущей умножением на матрицу
|1 1|
|1 0|
так что задача сводится к возведению матрицы в степень n. Это
можно сделать за C*log n действий тем же способом, что и для чи-
сел.
7.
То же, если требуется, чтобы количество операций
(выполненных команд присваивания) было бы не более C*n для не-
которой константы С.
Решение. Инвариант: sum = 1/1! +...+ 1/k!, last = 1/k!
(важно не вычислять заново каждый раз k!).
8.
Написать модифицированный вариант алгоритма Евкли-
да, использующий соотношения НОД (a, b) = НОД (a mod b, b) при
a >= b, НОД (a, b) = НОД (a, b mod a) при b >= a.
9.
Даны натуральные а и b, не равные 0 одновременно.
Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y.
Решение. Добавим в алгоритм Евклида переменные p, q, r, s
и впишем в инвариант условия m = p*a + q*b; n = r*a + s*b.
m:=a; n:=b; p := 1; q := 0; r := 0; s := 1;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0
m = p*a + q*b; n = r*a + s*b.}
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n; p := p - r; q := q - s;
| end else begin
| | n := n - m; r := r - p; s := s - q;
| end;
end;
if m = 0 then begin
| k :=n; x := r; y := s;
end else begin
| k := m; x := p; y := q;
end;
10.
Решить предыдущую задачу, используя в алгоритме
Евклида деление с остатком.
11. Проверить, является ли заданное натуральное число
n > 1 простым.
вот решения первой задачи :
double b = 0;
Console.WriteLine(" а");
int a = Int32.Parse(Console.ReadLine());
Console.WriteLine("n (Степень) ");
int n = Int32.Parse(Console.ReadLine());
if (n < 0)
{
Console.WriteLine("Переменная n невинного быть меньшая нуля");
}
else
{
b = Math.Pow(a, n);
}
Console.WriteLine("Ответ\n" + b);
Console.WriteLine();
Первые 5 задач: