Задачи на цикл для без массивов

В данной теме предлагаются решения простых задач с наименьшим числом действий (выполяемых операторов присваивания).

Задача 1. Дано число а и натуральное число n. Вычислить аn (a в степени n).

Решение:

k:=0; b:=1;

while k<>n do

begin

k:=k+1;

b:=b*a;

end;

Другое решение этой задачи:

k:=n;b:=1;

while k<>0 do

begin

k:=k-1;

b:=b*a;

end;

Число выполняемых операторов присваивания равно n.

Задача 2. Решить предыдущую задачу, если требуется, чтобы число действий (выполняемых операторов присваивания) было порядка log2n (то есть не превосходило бы C·log2n, где С -константа, log2n – это степень, в которую нужно возвести 2, чтобы получить n).

Решение:

k:=n; b:=1; c:=a;

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;

За каждые два вхождения в цикл значение переменной k уменьшается по крайней мере вдвое. В цикле выполняется 2 операции присваивания. Поэтому общее число действий не превосходит 4·log2n.

Задача 3. Дано натуральное число n, вычислить n! (1!=1, n!=n·(n-1)!).

Решение:

k:=n; b:=1;

while k<>0 do

begin

b:=b*k;

k:=k-1;

end;

Задача 4. Дано натуральное n, вычислить 1/1!+…+1/n! так, чтобы число операций (выполняемых команд присваивания) было бы порядка n (не более C·n для некоторой константы С).

Решение: Важно не вычислять заново каждый раз n!.

n!=1·2·3· … ·(n-1)·n=(n-1)!·n. В нашем примере 1/n!=1/((n-1)!·n), т.е. каждый j элемент получается делением (j-1)-го элемента на j.

k:=1; sum:=0; last:=1; {1/1!}

while k<=n do

begin

sum:=sum+last;

k:=k+1;

last:=last/k;

end;

Число выполняемых операций присваивания равно 3·n.

Задача 5. Даны два натуральных числа а и b, не равные нулю одновременно. Вычислить d=НОД(а,b) – наибольший общий делитель а и b.

Решение: Алгоритм Евклида. Будем считать, что

для всех а,b>=0.

(см. Основы информатики и вычислительной техники, часть 1, под ред. А.П. Ершова и В.М. Монахова или А.Г. Кушниренко и др. Основы информатики и вычислительной техники)

m:=a; n:=b;

while not ((m=0) or (n=0)) do

if m>=n then m:=m-n else n:=n-m;

if m=0 then d:=n else d:=m;

Задача 6. Даны два натуральных числа а и b, не равные нулю одновременно. Найти d=НОД(а,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;

while not ((m=0) or (n=0)) do

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;

if m=0 then

begin

k:=n; x:=r; y:=s;

end

else

begin

k:=m; x:=p; y:=q;

end;

Задача 7. Даны натуральные числа n и k, n>1. Напечатать k десятичных знаков числа 1/n. Программа должна использовать только целые переменные.

Решение: Сдвинув в десятичной записи числа 1/n запятую на k мест вправо, получим число (10k)/n. Нам надо напечатать его целую часть, то есть разделить 10k на n нацело. Стандартный способ требует использования больших по величине чисел, которые могут выйти за границы диапазона представимых чисел.

Воспользуемся методом “деления уголком” и будем хранить “остаток” r.

t:=0; r:=1;

while t<>k do

begin

write((10·r) div n);

r:=(10·r) mod n;

t:=t+1;

end;

Задача 8. Функция f с натуральными аргументами и значениями определена так: f(0)=0, f(1)=1, f(2n)=f(n), f(2n+1)=f(n)+f(n+1). Составить программу вычисления f(n) по заданному n, требующую порядка log2n операций (не более C·log2n).

Решение: Функцию f можно записать в общем виде: f(n)=a·f(k)+b·f(k+1).

Если n – четное, то а=1, b=0 иначе а=1, b=1.

Для k=2m: f(k)=f(m), f(k+1)=f(2m+1)=f(m)+f(m+1).

Тогда f(n)=a·f(k)+b·f(k+1)=a·f(m)+b·(f(m)+f(m+1))=(a+b)·f(m)+b·f(m+1).

Для k=2m+1: f(k)=f(m)+f(m+1), f(k+1)=f(2m+2)=f(2(m+1))=f(m+1).

Тогда f(n)=a·f(k)+b·f(k+1)=a·f(m)+(a+b)·f(m+1).

k:=n; a:=1; b:=0;

while k<>0 do

if k mod 2=0

then begin

m:=k div 2;

a:=a+b;

k:=m;

end

else begin

m:=k div 2;

b:=a+b;

k:=m;

end;

{k=0: f(n)=af(0)+bf(1)=b, что и требовалось}

При каждом вхождении в цикл значение переменной k уменьшается вдвое. Поэтому число операций не более 3·log2n.

Упражнения:

1. Последовательность Фибоначчи определяется так: a0=0, a1=1, ak=ak-1+ak-2 при k>=2.

Дано n. Вычислить an. Число операций должно быть порядка log2 n.

2. Написать вариант алгоритма Евклида, использующий соотношения НОД(2a,2b)=2НОД(a,b),

НОД(2a,b)=НОД(a,b) при нечетном b, использующий лишь деление на 2 и проверку четности. Число действий должно быть порядка log2n для исходных данных, не превосходящих n.

Источник

Решение задач на операторы цикла для обработки одномерных массивов. Циклы for, while, do…while

Содержание

Решения задач
- 1. Нахождение суммы элементов массива из n вещественных чисел
  - 1.1. Решение с использованием цикла for
  - 1.2. Решение с использованием цикла while
  - 1.3. Решение задачи. Цикл do…while
- 2. Нахождение среднего арифметического элементов массива из n вещественных чисел
  - 2.1. Решение. Цикл for
  - 2.2. Решение. Цикл while
  - 2.3. Решение. Цикл do…while
- 3. Поэлементное копирование массивов
  - 3.1. Цикл for
  - 3.2. Цикл while
  - 3.3. Цикл do…while
- 4. Обращение массива (получить результирующий массив, обратный к исходному)
- 5. Обращение массива без использования дополнительного массива
Связанные темы

Поиск на других ресурсах:

1. Нахождение суммы элементов массива из n вещественных чисел

1.1. Решение с использованием цикла for

// сумма элементов массива вещественных чисел const int MaxN = 100; int n; float A[MaxN]; float sum; // результат – сумма элементов массива // задать значение n n = 10; // заполнение массива A произвольными значениями for (int i=0; i<n; i++) A[i] = 0.1f * i; // сначала обнулить значение sum sum = 0; // цикл вычисления суммы for (int i=0; i<n; i++) sum = sum + A[i];

⇑

1.2. Решение с использованием цикла while

Решение задачи с использованием цикла while

// сумма элементов массива вещественных чисел – цикл while const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива float A[Max]; // массив float sum; // результат – сумма элементов массива int i; // дополнительная переменная // задать значение n n = 10; // заполнение массива A произвольными значениями через цикл while i=0; while (i<n) { A[i] = 0.1f*i; i++; } // сначала обнулить значение sum и i sum = 0; i = 0; // цикл while для вычисления суммы while (i<n) { sum += A[i]; i++; }

⇑

1.3. Решение задачи. Цикл do…while

// сумма элементов массива вещественных чисел – цикл do..while const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива float A[Max]; // массив float sum; // результат – сумма элементов массива int i; // дополнительная переменная // задать значение n n = 10; // заполнение массива A произвольными значениями через цикл do..while i=0; do { A[i] = 0.1f*i; i++; } while (i<n); // сначала обнулить значение sum и i sum = 0; i = 0; // цикл do..while для вычисления суммы do { sum += A[i]; i++; } while (i<n);

⇑

2. Нахождение среднего арифметического элементов массива из n вещественных чисел

Чтобы найти среднее арифметическое элементов массива, сначала нужно найти сумму элементов массива, а потом эту сумму поделить на число элементов массива.

⇑

2.1. Решение. Цикл for

В примере пропущен ввод массива и количества элементов массива n.

// среднее арифметическое элементов массива вещественных чисел – цикл for const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива float A[Max]; // массив float avg; // результат – среднее арифметическое int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // сумма вычисляется в переменной avg avg = 0; // цикл for для вычисления суммы for (i=0; i<n; i++) { avg += A[i]; } // вычисление среднего арифметического avg = avg / n;

⇑

2.2. Решение. Цикл while

В примере пропущен ввод массива и количества элементов массива n.

// среднее арифметическое элементов массива вещественных чисел – цикл while const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива float A[Max]; // массив float avg; // результат – среднее арифметическое int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // заполнение массива A произвольными значениями через цикл do..while i=0; do { A[i] = 0.1f*i; i++; } while (i<n); // сумма вычисляется в переменной avg avg = 0; i = 0; // цикл while для вычисления суммы while (i<n) { avg += A[i]; i++; } // вычисление среднего арифметического avg = avg / n;

⇑

2.3. Решение. Цикл do…while

В примере пропущен ввод массива и количества элементов массива n.

// среднее арифметическое элементов массива вещественных чисел – цикл do..while const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива float A[Max]; // массив float avg; // результат – среднее арифметическое int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // сумма вычисляется в переменной avg avg = 0; i = 0; // цикл do..while для вычисления суммы do { avg += A[i]; i++; } while (i<n); // вычисление среднего арифметического avg = avg / n;

⇑

3. Поэлементное копирование массивов

3.1. Цикл for

В данном примере приводится фрагмент кода, копирующий массив A из 10 вещественных чисел (float) в массив B.

// поэлементное копирование массивов – цикл for const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива float A[Max]; // массив-источник float B[Max]; // массив-назначение int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // цикл копирования A => B for (i=0; i<n; i++) { B[i] = A[i]; }

⇑

3.2. Цикл while

Фрагмент копирования массива A в массив B с использованием цикла while

// поэлементное копирование массивов – цикл while const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива float A[Max]; // массив-источник float B[Max]; // массив-назначение int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // цикл копирования A => B i=0; while (i<n) { B[i] = A[i]; i++; }

⇑

3.3. Цикл do…while

Реализация копирования массивов с использованием цикла do…while

// поэлементное копирование массивов – цикл do…while const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива double A[Max]; // массив-источник double B[Max]; // массив-назначение int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // цикл копирования A => B i=0; do { B[i] = A[i]; i++; } while (i<n);

⇑

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

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

В данном примере приводится реализация обращения массива с помощью трех известных операторов цикла.

// Получение обратного массива const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива double A[Max]; // массив-источник double B[Max]; // массив-назначение int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // решение задачи с помощью цикла do…while обратного копирования A => B i=0; do { B[i] = A[n-i-1]; i++; } while (i<n); // решение с помощью цикла for for (i=0; i<n; i++) B[i] = A[n-i-1]; // решение с помощью цикла while i=0; while (i<n) { B[i] = A[n-i-1]; ++i; }

⇑

5. Обращение массива без использования дополнительного массива

Задан массив A с n вещественных чисел. Реализовать операцию обращения массива без использования дополнительного массива.

В приведенном ниже коде реализовано обращение массива с использованием операторов циклов for, while, do…while.

Пусть задано следующее описание типов данных

// Обращение массива A const int Max = 100; // максимально-допустимое количество элементов массива int n; // n = 1..Max – заданное количество элементов массива double A[Max]; // массив-источник int i; // дополнительная переменная double t; // дополнительная переменная // ввод массива A и количества элементов массива n // …

Тогда решение задачи с использованием цикла do…while

// решение задачи с помощью цикла do…while обратного копирования A => B i=0; do { t = A[i]; A[i] = A[n-i-1]; A[n-i-1] = t; i++; } while (i < (n/2));

Решение задачи с использованием цикла for

// решение с помощью цикла for for (i=0; i<n/2; i++) { t = A[i]; // использование дополнительной переменной t A[i] = A[n-i-1]; A[n-i-1] = t; }

Решение задачи с использованием цикла while.

// решение с помощью цикла while i=0; while (i<n/2) { t = A[i]; A[i] = A[n-i-1]; A[n-i-1] = t; i++; }

⇑

Связанные темы

Примеры решения распостраненных задач с одномерными массивами
Примеры решения задач с использованием строк символов

⇑

Источник

Решение задач на операторы цикла для обработки одномерных массивов. Циклы for, while, do…while

Содержание

Решение задач
- 1. Нахождение суммы элементов массива из n вещественных чисел
  - 1.1. Решение с использованием цикла for
  - 1.2. Решение с использованием цикла while
  - 1.3. Решение задачи. Цикл do…while
- 2. Нахождение среднего арифметического элементов массива из n вещественных чисел.
  - 2.1. Решение. Цикл for
  - 2.2. Решение. Цикл while
  - 2.3. Решение. Цикл do…while
- 3. Поэлементное копирование массивов
  - 3.1. Цикл for
  - 3.2. Цикл while
  - 3.3. Цикл do…while
- 4. Обращение массива (получить результирующий массив, обратный к исходному)
- 5. Обращение массива без использования дополнительного массива
Связанные темы

Поиск на других ресурсах:

1. Нахождение суммы элементов массива из n вещественных чисел.

1.1. Решение с использованием цикла for

// сумма элементов массива вещественных чисел int n=10; // задать значение n float[] A = new float[n]; float sum; // результат – сумма элементов массива // задать значение n n = 10; // заполнение массива A произвольными значениями for (int i=0; i<n; i++) A[i] = 0.1f * i; // сначала обнулить значение sum sum = 0; // цикл вычисления суммы for (int i=0; i<n; i++) sum = sum + A[i];

1.2. Решение с использованием цикла while

Решение задачи с использованием цикла while

// сумма элементов массива вещественных чисел – цикл while int n = 10; // задать значение n float[] A = new float[n]; float sum; // результат – сумма элементов массива int i; // дополнительная переменная // заполнение массива A произвольными значениями через цикл while i=0; while (i<n) { A[i] = 0.1f*i; i++; } // цикл вычисления суммы // сначала обнулить значение sum и i sum = 0; i = 0; // цикл while для вычисления суммы while (i<n) { sum += A[i]; i++; }

1.3. Решение задачи. Цикл do…while

// сумма элементов массива вещественных чисел – цикл do..while int n = 10; // задать значение n float[] A = new float[n]; // массив float sum; // результат – сумма элементов массива int i; // дополнительная переменная // заполнение массива A произвольными значениями через цикл do..while i=0; do { A[i] = 0.1f*i; i++; } while (i<n); // цикл вычисления суммы // сначала обнулить значение sum и i sum = 0; i = 0; // цикл do..while для вычисления суммы do { sum += A[i]; i++; } while (i<n);

2. Нахождение среднего арифметического элементов массива из n вещественных чисел.

2.1. Решение. Цикл for

В примере пропущен ввод массива и количества элементов массива n

// среднее арифметическое элементов массива вещественных чисел – цикл for int n = 10; // n – количество элементов массива float[] A = new float[n]; // объявление массива float avg; // результат – среднее арифметическое int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // сумма вычисляется в переменной avg avg = 0; // цикл for для вычисления суммы for (i=0; i<n; i++) { avg += A[i]; } // вычисление среднего арифметического avg = avg / n;

2.2. Решение. Цикл while

В примере пропущен ввод массива и количества элементов массива n.

// среднее арифметическое элементов массива вещественных чисел – цикл while int n = 10; // n – количество элементов массива float[] A = new float[n]; // объявление массива float avg; // результат – среднее арифметическое int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // сумма вычисляется в переменной avg avg = 0; i = 0; // цикл while для вычисления суммы while (i<n) { avg += A[i]; i++; } // вычисление среднего арифметического avg = avg / n;

2.3. Решение. Цикл do…while

В примере пропущен ввод массива и количества элементов массива n

// среднее арифметическое элементов массива вещественных чисел – цикл do..while int n = 10; // n – количество элементов массива float[] A = new float[n]; // объявление массива float avg; // результат – среднее арифметическое int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // сумма вычисляется в переменной avg avg = 0; i = 0; // цикл do..while для вычисления суммы do { avg += A[i]; i++; } while (i<n); // вычисление среднего арифметического avg = avg / n;

3. Поэлементное копирование массивов

3.1. Цикл for

В данном примере приводится фрагмент кода, копирующий массив A из 10 вещественных чисел (float) в массив B.

// поэлементное копирование массивов int n = 10; // n – количество элементов массива float[] A = new float[n]; // массив-источник float[] B = new float[n]; // массив-назначение int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // цикл копирования A => B for (i=0; i<n; i++) B[i] = A[i];

3.2. Цикл while

Фрагмент копирования массива A в массив B с использованием цикла while

3.3. Цикл do…while

Реализация копирования массивов с использованием цикла do…while

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

В данном примере приводится реализация обращения массива с помощью трех известных операторов цикла.

// Получение обратного массива int n = 10; // n – количество элементов массива float[] A = new float[n]; // массив-источник float[] B = new float[n]; // обратный массив – результат int i; // дополнительная переменная // ввод массива A и количества элементов массива n // … // решение задачи с помощью цикла do…while обратного копирования A => B i=0; do { B[i] = A[n-i-1]; i++; } while (i<n); // решение с помощью цикла for for (i=0; i<n; i++) B[i] = A[n-i-1]; // решение с помощью цикла while i=0; while (i<n) { B[i] = A[n-i-1]; ++i; }

5. Обращение массива без использования дополнительного массива

В приведенном ниже коде реализовано обращение массива с использованием операторов циклов for, while, do…while.

Пусть задано следующее описание типов данных

// Обращение массива A int n = 10; // n – количество элементов массива double[] A = new double[n]; // обрабатываемый массив int i; // дополнительная переменная double t; // дополнительная переменная // ввод массива A и количества элементов массива n // …

Тогда решение задачи с использованием цикла do…while

// решение задачи с помощью цикла do…while обратного копирования A => B i=0; do { t = A[i]; A[i] = A[n-i-1]; A[n-i-1] = t; i++; } while (i < (n/2));

Решение задачи с использованием цикла for

// решение с помощью цикла for for (i=0; i<n/2; i++) { t = A[i]; // использование дополнительной переменной t A[i] = A[n-i-1]; A[n-i-1] = t; }

Решение задачи с использованием цикла while.

// решение с помощью цикла while i=0; while (i<n/2) { t = A[i]; A[i] = A[n-i-1]; A[n-i-1] = t; i++; }

Связанные темы

Одномерные массивы. Примеры решения задач на одномерные массивы. Массивы структур. Массивы классов
Многомерные массивы. Ступенчатые массивы

Источник