Скелет алгоритма

Любой алгоритм можно представить в виде следующей структуры:

Алгоритм сложения двух чисел

Программа должна ввести два числа, сложить их и вывести результат.

Для хранения исходных чисел придется использовать две ячейки памяти (переменных). Для хранения результата – еще одну.

Это простейший линейный алгоритм:

И на языке Fortran:

program add_2_numbers

real a,b,c

 write(*,*) 'Enter two numbers, please:'

 read(*,*) a,b

 c=a+b

 write(*,*) 'the result of ',a,'+',b,' is ',c

end program add_2_Numbers

После выполнения оператора вывода write(*,*) 'Enter two numbers, please:' на экране появится:

Enter two numbers, please:

Затем начинает выполняться оператор read(*,*) a,b и программа будет ждать, пока пользователь не введет 2 числа, например:

2

5

Эти числа присваиваются переменным a и b.

При выполнении оператора c=a+b компьютер сложит значения из переменных a и b и положит сумму в переменную с.

При выполнении оператора write(*,*) 'the result of ',a,'+',b,' is ',c на экране появится

 the result of 2.000000  + 5.000000 is 7.000000

Появляются операторы:

описания типа - real список переменных

ввода - READ(*,*) список ввода

вывода - WRITE(*,*) список вывода

присваивания переменная = выражение

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

Программа должна вывести модуль введенного числа.

Исходные данные: число.

Результат: модуль числа.

Алгоритм:

·        Ввод числа;

·        Проверка числа: если меньше 0, то меняется знак;

·        Вывод.

program abs

real a

 print *,'enter number'

 read *, a

 if (a<0) a=-a

 print 2,a

2 format('Absolute value of the number:',f10.3)

end program abs

Оператор format указывает, как выводить значение переменной а.

Если мы не должны менять значение переменной а (по условиям задачи, например, в подпрограмме), можно сделать с дополнительной переменной:

program abs

real a,b

 print *,'enter number'

 read *,a

b=a

 if (a<0) b=-a

 print 2,b

2 format('Absolute value of the number:',f10.3)

end program abs

Вариант 3:

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

program abs

real a

 print *,'enter number'

 read *,a

 if (a<0) then

 print 2,-b

else

 print 2,b

end if

2 format('Absolute value of the number:',f10.3)

end program abs

Программа запрашивает число и выводит текстовое сообщение о его знаке.

3 варианта с разными IF.

Исходные данные: число

Результат: текстовое сообщение (одно из трех возможных)

Алгоритм:

• Ввод числа
• Проверка:
• если число <0,то вывод сообщения «число меньше 0»
• если число =0,то вывод сообщения «число равно 0»
• если число >0,то вывод сообщения «число больше 0»

Вариант программы с использованием арифметического условного оператора:

Program sign_of_number_0

implicit none

integer i

  print*,'Enter number'

 read *,i

 if (i) 2,5,4

2 print *,'number is negative'

 goto 10

5 print *,'number is equal to zero'

 goto 10

4 print *,'number is pozitive'

10 continue

end program sign_of_number_0

Вариант программы с использованием логического условного оператора:

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

Вариант программы на языке С:

#include <stdio.h>

void main(void)

{

 int i;

 printf("Enter number ");

 scanf("%d",&i);

 if (i<0) printf("number is negative");

 else if (i==0) printf("number is equal to zero");

 else printf("number is pozitive");

}

_______________________________________________________________________________________________

Программа меняет значения 2-х переменных.

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

1. арбуз из правой руки (b) положить на стол (c),
2. переложить арбуз из левой руки (a) в правую (b);
3. в левую руку (c) взять арбуз со стола.

Другая аналогия - 2 чашки, одна с кофе (a), другая - с чаем (b). Нужно поменять содержимое этих чашек. Действия аналогичные:

1. чай (b) переливаем в пустую чашку (c);
2. в чашку (b) переливаем кофе (a);
3. наливаем в чашку (a) чай из (с).

real a,b,c

print *,'Enter 2 numbers '

read (*,*) a,b

c=b

b=a

a=c

print *,'a=',a,'b=',b

end

Несколько необычный, (да и ничем не лучший) вариант без использования дополнительной переменной:

_______________________________________________________________________________________________

Составить программу для вычисления значения функции y=3*x⁵+5*x²-2*x-3, значение x задается пользователем.

Исходные данные: значение х

Результат: значение y (1 число)

Алгоритм:

·        Ввод числа в переменную x;

·        Подставить в формулу, вычислить значение и поместить в переменную y;

·        Вывод.

program p4

implicit none

real x,y

 print *,'enter x'

 read *,x

 y=3*x**5+5*x**2-2*x-3

 print *,'y=',y

end program p4

___________________________________________________________________________________

Составить программу для вычисления значения системы функций , значение x задается пользователем.

Исходные данные: значение х.

Результат: значение y (1 число).

Алгоритм:

·        Ввод числа в переменную x;

·        Подставить в систему (найти соответствующую формулу), вычислить значение и поместить в переменную y;

·        Вывод.

program p3_2

implicit none

real x,y

 print *,'enter x'

 read *,x

 if (x>0) then

 y=3*x**5+5*x**2-2*x-3

 else if (x==0) then

 y=0

 else

 y=x**4+4

 end if

 print *,'y=',y

end program p3_2

________________________________________________________________________________

Составить программу для вычисления значения функции y=3*x⁵+5*x²-2*x-3, значение x выбираются с шагом 0.1 из интервала [-5...5].

Исходные данные: нет.

Результат: значения y (несколько чисел).

Алгоритм:

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

·        1) Принять х равным началу диапазона (-5);

·        2) Подставить в уравнение и найти значение у;

·        3) Записать полученное значение у;

·        4) Взять следующее значение х путем прибавления к предыдущему шага 0.1;

·        5) перейти к пункту 2 , если х£5.

Вариант программы с выводом результатов в виде таблицы

program p4_1

implicit none

real x,y

 x=-5

 print 3

 1 y=3*x**5+5*x**2-2*x-3

 print 2,x,y

 x=x+0.1

 if (x<5.01) goto 1

3 format('| x  | y |',/,'____________________')

2 format('| ',f6.2,' | ',f8.2,'|')

end program p4_1

Однако лучше не использовать оператор go to, а заменить его на конструкцию DO - цикл.

_________________________________________________________________________________________

Составить программу для вычисления значения функции y=3/x, значение x выбираются с шагом 0.1 из интервала [-5...5].

Исходные данные: нет.
Результат: значения y (несколько чисел).
Алгоритм: аналогично предыдущему примеру.

program p4_6

implicit none

real x,y

 x=-5

1 if (x==0) then

  print*,'y(0)=*****'

 else

  y=3/x

  print *,'y(',x,')=',y

 end if

 x=x+0.5

 if (x<5.01) goto 1

end program p4_6

______________________________________________________________________________________

Вычисление суммы и произведения.

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

Пример: сложить первые 10 натуральных чисел

S=0

Do i=1,10 ! (по кол-ву слагаемых)

S=S+i

End do

Пример: вычисление определенного интеграла.

Аналогично с произведением, только перед циклом переменная приравнивается 1.

______________________________________________________________________________________

Определение факториала числа.

Алгоритм:
Факториал некоторого числа N равен 1*2*3*...*N. Из формулы видно, что последовательность действий сводится к повторению N раз двух действий:

• вычисления следующего числа (множителя) по формуле i=i+1;
• умножения предыдущего результата на множитель.

Integer:: i=1,N,f=1 
Print *,'введите число' 
Read*,N   

! вычисление факториала числа N 
  do 
     f=f*i ! результат пред. умножается на сл. число
     i=i+1 ! вычисление след. множителя
     if (i>N) exit
  end do 
! вывод результата 
  Print*,'факториал ',N,'=',f 
end 

Integer:: i=2,N,f=1 
Print *,'введите число' 
Read*,N   

! вычисление факториала числа N 
  do while(i<=N)
     f=f*i  
     i=i+1  
  end do 
! вывод результата 
  Print*,'факториал ',N,'=',f 
end 
	

Integer:: i,N,f=1
Print *,’введите число’ 
Read*,N   

! вычисление факториала числа N 
  do i=1,N 
     f=f*i 
  end do 
! вывод результата 
  Print*,’факториал ’,N,’=’,f 
end 

_________________________________________________________________________

Программа для разбора строки на правильное кол-во скобок

Вводит строку и проверяет, равняется ли количество открывающих скобок количеству закрывающих.

program ftst

implicit none

!a code fragment to check for balanced parentheses:

CHARACTER (80) :: LINE

integer i,level

!...

print *,"Enter line"

read(*,*) line

LEVEL = 0

SCAN_LINE: DO I = 1, 80

CHECK_PARENS: SELECT CASE (LINE (I:I))

CASE ('(')

 LEVEL = LEVEL + 1

CASE (')')

 LEVEL = LEVEL - 1

 IF (LEVEL < 0) THEN

 PRINT *, 'UNEXPECTED RIGHT PARENTHESIS'

 EXIT SCAN_LINE

 END IF

CASE DEFAULT

! Ignore all other characters

END SELECT CHECK_PARENS

END DO SCAN_LINE

IF (LEVEL > 0) THEN

print *,'error'

end if

end program ftst

__________________________________________________________________________________________

Найти квадратный корень числа А по итерационной формуле Ньютона

Y_n+1=1/2*(Y_n+A/Y_n), Y₀=А

с заданной точностью.

Найти 2 отличия:

1)      в операторе Yn=1/2*(y+x/y) при вычислении 1/2 ==0! Можно использовать 1./2 или 0.5.

2)      If (abs(yn-y)>eps) exit – истинно всегда!

Несколько замечаний:

Проверку можно было организовать исходя из смысла задачи - if (abs(x/y-y)<eps) ... Но в этом случае больше вероятность получить бесконечную рекурсию.

Вообще говоря, тут нужна проверка на зацикливание, так как процесс может не сходиться!

Этот алгоритм можно реализовать и в рекурсивной форме.

__________________________________________________________________________________________

Написать программу для нахождения значения функции

F(x)=1+1/2+1/4+1/8+…+1/(2*i)+… с заданной точностью eps

Значения первых нескольких последовательных приближений функции:

Обозначим значения функции F(x) переменной s, а значения очередного члена ряда – h.

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

Si=S_i-1+h_i

Теперь определим, как найти h_i.

Очевидно, что h_i=1/(2*i)

(h₀=0,h₁=1,h₂=1/2,h₃=1/4,…)

Тогда получаем следующий алгоритм:

• инициализация переменных (S);
• организация цикла;
• вычисление i-ого шага;
• вычисление очередного (i-ого) приближения функции;
• проверка на завершение цикла.

Проверка на завершение – определение истинности условия окончания цикла. Определим это условие. Каждый новый шаг цикла приближает нас к точному значению. Тогда можно принять этим условием (h<eps).

Теперь переводим на Fortran. Воспользуемся конструкцией бесконечного цикла:

implicit none

integer i

real eps,s,h

 print *,'введите точность'

 read *,eps

! инициализация

 i=1

 s=1

! основной цикл

 do

 h=1./(2.*i) ! лучше 0.5/i

 s=s+h

 if (h<eps) exit

 i=i+1

 end do

 print *,'s=',s

end

______________________________________________________________________________________

Найти значение числа e с помощью ряда

 e=1+1/1!+1/2!+1/3!+….1/n!

Разбираем последовательность:

e=1

e=1+1/1=e+1=2

e=1+1/1+1/2!=e+1/2! – это обычное вычисление суммы

Теперь определим, как находить каждый новый элемент суммы

e_i+1=e_i+S_i, S_i=1/i!  - можно честно вычислять факториал каждый раз

Но это жутко неэффективно!

Посмотрим, как меняется S_i  каждый раз:

S_i+1= S_i/i - вот готовая формула

В программе воспользуемся циклом с предусловием:

! программа вычисления числа e

implicit none

Real e,S,eps

integer i

  print *,'введите точность'

 read *,eps

! инициализация

 e=2

 S=1

 i=2

! основной цикл

 do while(S>eps)

  S=S/i

  e=e+S

  i=i+1

 end do

 Print *,i,e-exp(1.)

end

____________________________________________________________________________________

Определить, кратно ли одно число другому?

Надо вспомнить о преобразовании типов в арифметических операциях (см. раздел об арифметических операциях).

Так как 5/2*2->2*2->4, кратность можно определить следующим способом

Integer a,b

Print *,'enter a,b'

do

 Read *,a,b

 if (b==0) exit

 If (a/b*b==a) then

 print *,a,' kratno ',b

 else

 print *,a,' NOT kratno ',b

 end if

end do

End

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

real a,b

real a1,b1

Print *,'enter a,b'

do

 Read *,a,b

 if (b==0) exit

 b1=INT(a/b)

 a1=a/b

 If (a1-b1==0) then

 print *,a,' kratno ',b

  else

 print *,a,' NOT kratno ',b

 end if

 end do

 End

Здесь мы неявно выделили остаток от деления одного числа на другое

a/b-INT(a/b)

Чтобы выделить остаток от деления а на b, можно воспользоваться следующим приемом

Rem=a - INT(a / b) * b

Но это же самое делает встроенная функция mod(a,b).

if (mod(a,b)==0) print*,'число a кратно b'

________________________________________________________________________________________

Сортировка массива

implicit none

real a(10),b,a1(10)

integer i,j

logical :: flag=.true.

! задание начальных значений массива a по датчику случайных чисел

do i=1,10

  call random_number(a) ! – заполнить массив случайными числами

 ! a(i)=REAL(rand(0)) – в стандарте нет функции rand

end do

a1=a  ! сохраним старые значения массива для дальнейшего вывода

do while(flag)

 flag=.false.

 do j=1,9

 if (a(j)>a(j+1)) then

 b=a(j)

 a(j)=a(j+1)

 a(j+1)=b

 flag=.true.

 end if

 end do

end do

print *,a

print *,a1

end

_______________________________________________________________________________

В массиве A(3,5,7) найти максимальное число. Использовать встроенную функцию MAX(a,b,…).

Так как массив трехмерный, надо использовать три вложенных цикла:

do i=1,3

 do i=1,5

 do k=1,7

 …..

 end do

 end do

end do

Но, так как все элементы располагаются в памяти компьютера последовательно, можно обратиться к памяти, занимаемой массивом A(3,5,7), как к одномерному массиву T(3*5*7). Для этого воспользуемся оператором Equivalence(наложения переменных).

Implicit none

Integer A(3,5,7),T(3*5*7)

Equivalence (A(1,1,1),T(1))

Integer m

Read (*,*) a

M=T(1)

Do i=2,3*5*7

 M=MAX(T(i),M)

End do

End

_______________________________________________________________________________

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

Простыми являются целые положительные числа, которые делятся нацело ТОЛЬКО на 1 и на самих себя.

Исходные данные – собственно, для решения данной задачи никаких исходных данных не нужно.

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

Вариант 1

Будем перебирать все положительные целые числа, пока не наберем 10 простых.

Очевидно, что первыми простыми являются числа 1 и 2. Тогда можно начать перебор с 3. Пусть N – текущее целое положительное число. Тогда вариант 1 запишется так:

Вариант 2

N=3

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

 Если N – простое число То сохранить значение N

 N=N+1

Конец  

Жирным шрифтом выделены те действия (команды), которые на самом деле не являются простейшими, т.е. не могут быть выполнены исполнителем. Их придется детализировать. Первое – количество найденных простых чисел. Это не что иное, как некоторое число. Введем для него дополнительную переменную - k. С учетом первых «тривиальных» простых – 1 и 2, первоначальное значение k равно 3.

Вариант 3

N=3

k=3

Пока k не больше 10 повторять:

 Если N – простое число То:

сохранить значение N под номером k

k=k+1

 Конец если

 N=N+1

Конец  

Как осуществить проверку простое число? Ключевым определения простых чисел является слово ТОЛЬКО! Следовательно, проверку можно организовать «от обратного» – если найдется хотя бы одно число m, больше 1, при делении на которое исходного числа N остаток равен 0, то N – не простое. Для этого достаточно перебрать все числа в диапазоне 1… N

Подвариант 3.1

  Повторять i=2 до N-1

  Если остаток от N/I равен 0 То N не простое

  Конец

«N не простое» - не просто констатация факта. Это новая полученная информация, которая понадобится после этого цикла. Следовательно, ее нужно сохранить, например, в какой-то логической переменной: IsPrime=ЛОЖЬ. Исходя из «презумпции невиновности» перед проверкой предположим, что N – простое. Как только определили, что это не так – можно прекращать проверку – совершенно не важно, сколько еще чисел являются делителями N.

Подвариант 3.2

IsPrime=ПРАВДА

  Повторять i=2 до N-1

  Если остаток от N/I равен 0 То:

 IsPrime=ЛОЖЬ

Прекратить повторять

Конец если

  Конец

Теперь разберемся с командой «сохранить значение N под номером k». Если мы хотим сохранить все найденные значения N, то нам придется использовать массив (только массив позволяет под одним именем хранить несколько значений одновременно), например, Primes. Тогда мы получаем «сохранить в ячейке массива Primes под номером k», или

 Primes(k)=N

Если собрать все вместе:

Вариант 4

N=3

k=3

Пока k не больше 10 повторять:

IsPrime=ПРАВДА

  Повторять i=2 до N-1

  Если остаток от N/I равен 0 То:

 IsPrime=ЛОЖЬ

Прекратить повторять

Конец если

  Конец

Если IsPrime=ПРАВДА То: (комментарий: N – простое число )

  Primes(k)=N

k=k+1

 Конец если

 N=N+1

Конец  

Поскольку не осталось «темных мест», можно переходить к кодированию, например на Fortran-е. Для этого достаточно заменить ключевые слова моего псевдокода аналогичными ключевыми словами Fortran-а.

implicit none

integer i,k,N

integer Primes(10)

logical IsPrime

 Primes(1)=1

 Primes(2)=2

 N=3

 k=3

 do while(k<=10)

 IsPrime=.TRUE.

  do i=2,N-1

  if (mod(N,I)==0) then

 IsPrime=.FALSE.

 exit

 end if

  end do

 if (IsPrime) then

  Primes(k)=N

 k=k+1

  end if

  N=N+1

 end do

 print *,Primes

end

Любую программу можно улучшать до бесконечности. Эта – не исключение. Можно подумать об эффективности – внутренний цикл нет смысла повторять до N-1.

_____________________________________________________________________________________

Задача: найти среднее арифметическое данных, полученных в результате эксперимента.

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

Итак, алгоритм получается следующий:

1. Ввод исходных данных
2. нахождение максимального и минимального.
3. получение новой последовательности без max и min
4. нахождение среднего

1.  Поскольку нам несколько раз надо будет иметь доступ к исх. данным, придется занести их в массив.

real Arr(100)

print *,’ введите количество чисел’

read *,N

print *,’введите числа’

do i=1,N

 read *,Arr(i)

end do

Надо добавить описание переменных i,N и сделать проверку вводимых значений N на допустимость. В случае если пользователь ввел недопустимое значение N (больше 100) дадим ему возможность повторить ввод хотя бы 5 раз. Для этого воспользуемся циклом со счетчиком.

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

real  Arr(100)

integer i,N

do i=1,5

  print *,’ введите количество чисел’

read *,N

if (i>0 .and. i<=100 ) exit

end do

print *,’введите числа’

do i=1,N

 read *,Arr(i)

end do

2. Поиск max и min осуществим перебором всех значений массива. Рассмотрим на примере поиска max:

Рассмотрим последовательность, состоящую из одного числа (Arr(1)). Оно и есть максимальное. Сохраним его для последующего использования в переменной a_max.

a_max=Arr(1)

Добавим к последовательности  следующий элемент массива и найдем max:

if (Arr(2)> a_max) a_max=Arr(2)

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

if (Arr(i)> a_max) a_max=Arr(i)

Следовательно, выполнив эту операцию N-1 раз, мы получим результат. Для этого воспользуемся циклом:

a_max=Arr(1)

do i=2,N

if (Arr(i)> a_max) a_max=Arr(i)

end do

Для нахождения min надо использовать тот же алгоритм, только использовать другую переменную (назовем ее a_min) и при проверке заменить знак > на <. А саму проверку можно осуществить в том же цикле.

real Arr(100), a_max, a_min

integer i,N

do i=1,5

  print *,’ введите количество чисел’

read *,N

if (i>0 .and. i<=100 ) exit

end do

print *,’введите числа’

do i=1,N

 read *,Arr(i)

end do

! ищем max и min

a_max=Arr(1)

a_min=Arr(1)

do i=2,N

if (Arr(i)> a_max) a_max=Arr(i)

if (Arr(i)< a_min) a_min=Arr(i)

end do

3. Теперь перенесем все числа из исходного массива Arr в новый (например, Brr) за исключением a_max и a_min.

Простейший вариант

do i=1,N

 if (Arr(i)/=a_max .or. Arr(i)/=a_min ) Brr(i)=Arr(i)

end do

не годится по двум причинам. Во-первых, ячейкам массива Brr с номерами, равными номерам ячеек массива Arr, где находились значения, равные a_min и a_max, не будет присвоено никаких значений (они будут находиться в неопределенном состоянии). Если возникли сложности с переводом предыдущей фразы на русский язык, можно рассмотреть результат работы этого алгоритма на примере:

Arr Brr

1  -> 1

-2 min ?

-1 -> -1

5  max ?

3  -> 3

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

 Найти номера максимального и минимального элемента (запомним их в дополнительных переменных, например n_min, n_max);

 Переносим в массив Brr(i) все элементы из массива Arr(i) кроме имеющих номера n_min, n_max.

! ищем max и min и их номера

a_max=Arr(1)

a_min=Arr(1)

n_max=1

n_min=1

do i=2,N

if (Arr(i)> a_max) then

 n_max=i

a_max=Arr(i)

 end if

if (Arr(i)< a_min) then

 n_min=i

a_min=Arr(i) 

 end if

end do

!  перенесем в массив Brr

k=0

do i=1,N

 if (i/=n_max .and. i/=n_min) then

 k=k+1

Brr(k)=Arr(i)

 end if

end do

Для второй части нам пришлось воспользоваться дополнительной переменной k, с помощью которой мы явно меняем значение индекса (номера) элемента массива Brr.

4.  Нахождение среднего. Надо сложить N-2 элементов массива Brr и разделить на

N-2.

Sr=Brr(1)

do i=2,N-2

Sr=Sr+Brr(i)

end do

print *,’среднее значение =’, Sr/(N-2)

В результате получим следующий вариант программы:

implicit none

real Arr(100),Brr(100),a_max,a_min,Sr

integer i,N,n_max,n_min,k

!  ввод данных

do i=1,5

   print *,' введите количество чисел'

read *,N

if (i>0 .and. i<=100 ) exit

end do

print *,'введите числа'

do i=1,N

 read *,Arr(i)

end do

!  ищем max и min и их номера

a_max=Arr(1)

a_min=Arr(1)

n_max=1

n_min=1

do i=2,N

if (Arr(i)> a_max) then

  n_max=i

  a_max=Arr(i)

end if

if (Arr(i)< a_min) then

 n_min=i

  a_min=Arr(i) 

end if

end do

! перенесем в массив Brr

k=0

do i=1,N

 if (i/=n_max .and. i/=n_min) then

 k=k+1

 Brr(k)=Arr(i)

 end if

end do

! найти среднее

Sr=Brr(1)

do i=2,N-2

  Sr=Sr+Brr(i)

end do

print *,'среднее значение =', Sr/(N-2)

end

_______________________________________________________________________________________

  Найти в массиве второй по величине элемент.

Общая структура алгоритма:

1.                  Ввод данных

2.                  Нахождение элемента

3.                  Вывод результата

Первая часть разбиралась уже не раз.

Вторая часть.

Как всегда вариантов решения задачи много. Например, найти максимальное значение, выкинуть его, снова найти максимальное. Первый цикл для поиска максимального элемента, второй цикл – для копирования в другой массив всех элементов, кроме найденного, третий цикл – для повторного поиска максимального в новом массиве.

implicit none

real ar(10),br(10),m_max,n_max

integer i,j,N

! Ввод массива

 print *,’ введите количество чисел’

 read *,N

 print *,’введите числа’

 do i=1,N

 read *,ar(i)

 end do

! Поиск максимума

 m_max=ar(1)

 n_max=1

 do i=2,N

 if (m_max<ar(i)) then

 m_max=ar(i)

 n_max=i

 end if

 end do

! Копирование в соседний массив

 j=1

 do i=1,N

 if (i/=n_max) THEN

 br(j)=ar(i)

 j=j+1

 end if

 end do

! Повторный поиск максимума

  m_max=br(1)

 do i=2,N

 if (m_max<br(i))  m_max=br(i)

  end do

 print *,m_max

end

Другой вариант – после первого поиска максимума разделить массив на два – с первого элемента до m_max (не включая его) и со следующего до последнего элемента. Затем найти максимальные элементы в обоих подмассивах и сравнить их. Максимальный из них и будет искомым. 

Следующий вариант - сортировка всего массива по возрастанию. Тогда предпоследний элемент и есть искомый.

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

……

! Поиск максимума

  m_max=ar(1)

  n_max=1

 do i=2,N

 if (m_max<ar(i)) then

 m_max=ar(i)

 n_max=i

 end if

 end do

! Повторный поиск максимума

 if (n_max/=1) then

 m_max=ar(1)

 else

 m_max=ar(2)

 end if

 do i=2,N

 if (n_max/=i .and. m_max<ar(i)) then

 m_max=ar(i)

 end if

 end do

 print *,m_max

end

Но и этот алгоритм можно усовершенствовать. Так ли нужен второй цикл?

Попробуем искать сразу и максимальный элемент и второй по величине. Нам придется ввести еще одну переменную m_max1. Для каждого элемента массива ar надо рассматривать два случая: ar(i) больше m_max – в этом случае надо заменить значение m_max на ar(i); или ar(i) больше m_max1 – в этом случае надо заменить значение m_max1 на ar(i). Но в первом случае стоит вспомнить,  что первоначальное значение m_max – самое большое из найденных и больше m_max1, следовательно, при смене m_max на новое большее значение старое становится вторым по величине и заслуживает запоминания в m_max1.

implicit none

real ar(10),br(10),m_max,m_max1

integer i,j,N

! Ввод массива

 print *,’ введите количество чисел’

 read *,N

 print *,’введите числа’

 do i=1,N

 read *,ar(i)

 end do

! Чуть больше возни с выбором начальных значений

 if (ar(1)>ar(2)) then

 m_max=ar(1)

  m_max1=ar(2)

 else

 m_max=ar(2)

 m_max1=ar(1)

 end if 

 do i=2,N

 if (m_max<ar(i)) then

 m_max1=m_max

 m_max=ar(i)

 else if (m_max1<ar(i)) then

 m_max1=ar(i)

 end if

 end do

 print *,m_max1,m_max

end

________________________________________________________________________________

Программа должна вывести адрес числа (задаваемого пользователем) в массиве с помощью дихотомии (составил Мещеряков Д.В.)

 Массив содержит числа, отсортированные по возрастанию. Дихотомию еще называют методом половинного деления.

Итак, алгоритм задачи:

0.  Начало программы.

1. Ввод возрастающей последовательности.
2. Ввод искомого числа.
3. Поиск заданного значения и его адреса.
4. Вывод результата.
5. Завершение программы.

0. В начало программы можно включить описание переменных и массивов и присваивание им начальных значений.

 program D

  implicit none 

  integer Arr(100),m,n,x,a,b,I

 Arr=0

m=0

n=0

x=0

a=0

b=0

I=0

1. Ввод последовательности можно осуществить разными способами, но мы пойдем по самому простому пути.

!  Ввод предела последовательности

do while (0>n.or.n>100.or.m>n)

write (*,*) 'Vvedite kollichestvo znachenie N'

read (*,*) n

end do

 ! Заполнение массива  в порядке возрастания (от a до b)

do I=1,n

  Arr(I)=I

end do

2. Ввод искомого числа адрес которого нам надо найти.

write (*,*) 'Vvedite iskomoe chislo' 

 read (*,*) x

3. Поиск заданного значения и его адреса в массиве.

! Условно разделим наш массив на 2 части. Начало левой части будет присвоено

! переменной а, а конец переменной b.

a=1

 b=(n-a)/2

 ! Если искомое число не лежит в выбранной части, то берем второй и делим его

! пополам (соответственно началом и концом правой половины массива служат

! значения переменных а и b).

! Цикл do while предназначен для завершения поиска.

do while (Arr(a)/=x.and.Arr(b)/=x)

  if (Arr(a)<x.and.x<Arr(b)) then 

  a=a

  b=a+(b-a)/2

  else

    a=b

  b=a+(n-a)/2

  end if

 end do

4. Вывод результата.

if (Arr(a)==x) write (*,10) Arr(a),x,a

 if (Arr(b)==x) write (*,10) Arr(b),x,b

10 Format ('Naidenoe=',I3,3x,'Iskomoe X=',I3,3x,'Adress Arr(', I3,')')

5. Завершение программы.

  end program D

Теперь все объединим .

 program Dix
 implicit none
 integer Arr(100),n,x,a,b,c,I,p
 
 do 
  write (*,*) 'Vvedite N'
  read (*,*) n
  if (n>0.and.n<=100) exit
 end do 
 N=100

 do I=1,n,1
  Arr(I)=I
 end do
 
 write (*,*) 'Vvedite iskomoe chislo' 
 read (*,*) x

 
 a=1
 c=n
 p=0 

 do 
    if (a>c) exit

    b=(c+a)/2    

    if (x == Arr(b)) then 
     p=b
     exit 
    elseif (x < Arr(b)) then 
     c=b-1
    else 
     a=b+1
   end if
 end do
 
 if (p==0) then
   write (*,*) 'Element not found'
 else 
   write (*,10) Arr(b),x,b
 end if
10 Format ('Naidenoe=',I3,3x,'Iskomoe X=',I3,3x,'Adress Arr(', I3,')')

 end program Dix

________________________________________________________________________________

module art
!модуль содержит описание интерфейса функции умножения
interface 
	integer  function mult(a,b)
	 integer a,b
	end function mult
end interface
end module art

module art1
!модуль содержит описание интерфейса функции возведения в степень
interface 
	integer function pwr(a,b)
	 integer a,b
    end function pwr
end interface 
end module art1

!____________________________________________________________________!
!Главная программа
use art1
implicit none
 integer x,y
 print *,'enter x,y'
 read *,x,y

 print *,pwr(x,y),x**y
end 

!____________________________________________________________________!
!Подпрограмма вычисления возведения неотрицательного целого числа  в 
!неотрицательную целую степень через умножение.

integer function pwr(x,y) 
! calculate x**y
use art
implicit none 
integer x,y,j
 pwr=x
 do j=2,y
  pwr=mult(pwr,x)
 end do
end

!____________________________________________________________________!
!Подпрограмма вычисления произведения двух неотрицательных целых чисел 
!через сложениие.

integer function mult(a,b)
! calculate a*b
implicit none 
integer a,b,i
	mult=0
	do i=1,b
		mult=mult+a
	end do
end

________________________________________________________________________________

Найти в одномерном массиве упорядоченные по возрастанию подпоследовательности

 implicit none
 integer :: a(10),n=10,res(10)
 
! print *,'enter numbers'
! read *,(a(i),i=1,n)
 a=(/1,2,3,4,2,7,2,4,5,7/)
 print *,a
call search1(a,n,res)
 print '(10i3)',res
call search(a,n,res)
 print '(10i3)',res

 a=(/1,2,3,4,5,6,7,8,9,9/)
 print *,a
 call search1(a,n,res)
 print '(10i3)',res
call search(a,n,res)
 print '(10i3)',res

 a=(/10,9,8,7,6,5,4,3,2,1/)
 print *,a
 call search1(a,n,res)
 print '(10i3)',res
call search(a,n,res)
 print '(10i3)',res

 a=(/1,2,1,2,1,2,1,3,1,1/)
 print *,a
 call search1(a,n,res)
 print '(10i3)',res
call search(a,n,res)
 print '(10i3)',res


end 


! вариант первый - все время считаем длину (l=l+1) 

subroutine search1(a,n,r)
 implicit none
 integer :: a(*),n,i,l,r(n),k
 k=1
 r=0
 l=1
 do i=1,n-1
   if (a(i)>a(i+1)) then
    if (l>1) then
     r(k)=l
     k=k+1
    end if
	l=1
   else 
    l=l+1
   end if
 end do
 if (l>2) then
  r(k)=l
  k=k+1
 end if 
end 

! вариант второй - запоминаем начало последовательности, 
! когда доходим до пограничного элемента - считаем длину подпоследовательности
subroutine search(a,n,r)
 implicit none
 integer :: a(*),n,b,i,l,r(n),k
 b=1
 k=1
 r=0      ! для определения количества заполненных
 do i=1,n-1
   if (a(i)>a(i+1)) then
    l=i-b+1
    if (l>1) then
     r(k)=l
     k=k+1
    end if
    b=i+1
   end if
 end do
 ! последняя группа
 l=n-b+1
 if (l>2) then
  r(k)=l
  k=k+1
 end if 
end

________________________________________________________________________________

Написать программу, которая определяет количество несократимых дробей вида p/q
среди натуральных (целых положительных) чисел, при условии что p+q<100.

Начнем с главной программы.
Очевидно, что оба числа должны находиться в диапазоне 1-98. Следовательно,
внешний цикл будет следующим:

do p=1,98
Внутренний цикл можно сделать таким же, и проверять внутри условие p+q<100
do q=2,98
if (p+q>=100) continue
Но это не эффективно. Лучше немного подумать о том, как может изменяться вторая переменная.
Тогда мы получим 2 цикла:
do p=1,98
do q=2,100-p
Условие "несократимости" дроби сводиться к нахождению общих делителей числителя и знаменателя.
Для этого можно написать подпрограмму.
s=0 ! начальное значение счетчика
do p=1,98
do q=2,100-p
if (hasNOD(p,q)) s=s+1 ! hasNOD - подпрограмма для определения "несократимости"
end do
end do
print *,s
end

Подпрограмма будет выглядеть как-то так
function hasNOD(a,b)
logical hasNOD
integer a,b
hasNOD=true
if ( есть хотя бы 1 общий делитель) hasNOD=false
end

Как определить наличие общего делителя? Придется перебрать все числа, меньшие наименьшего из a и b.
do i=2,min(a,b)
if (mod(a,i)==0 .and. mod(b,i)==0) then
hasNOD=false
return ! позволяет выйти из программы сразу без перебора всех остальных возможных делителей.
end if
end do

В результате получим следующее:

  integer s,p,q
  logical hasNOD
   s=0 				! начальное значение счетчика
   do p=2,98
    do q=2,100-p
     if (hasNOD(p,q)) s=s+1
    end do
   end do
   print *,s
  end 

  function hasNOD(a,b)
  logical hasNOD
  integer a,b
   hasNOD=.true.
   do i=2,min(a,b)
  	if (mod(a,i)==0 .and. mod(b,i)==0) then
       hasNOD=.false.
	   return 					                              ! позволяет выйти из программы сразу без перебора всех остальных возможных   делителей.
  	end if
   end do
  end
  

Но главную программу можно слегка сократить, если изменить интерфейс подпрограммы:)

integer :: p,q,s=0
  integer hasNOD
  do p=2,98
  	do q=2,100-p
	  s=s+hasNOD(p,q)
	end do
  end do
  s=s+99				! Почему +99? - я  убрал одну итерацию внешнего цикла с p=1, так как это дает тривиальный результат типа 1/q
  print *,'Found ',s,' numbers'
  end
  
function hasNOD(a,b)
  integer hasNOD,a,b,i
  hasNOD=1
  do i=2,min(a,b)
  	if (mod(a,i)==0 .and. mod(b,i)==0) then
  		hasNOD=0
  		return
  	end if
  end do
  end
  

________________________________________________________________________________

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

subroutine full_sort(a,n,k)
implicit none
integer :: n,k,a(n,k),i,l
logical IsSorted
 do
  IsSorted=.true.
  do i=1,n-1
   do l=1,k
    if (a(i,l)/=a(i+1,l)) exit
   end do
   if (l>k) cycle
   if (a(i,l)>a(i+1,l)) then
     call swap_lines(a(i,:),a(i+1,:),k)
     IsSorted=.false.
    end if
  end do
  if (IsSorted) exit
 end do
end 

subroutine swap_lines(a1,a2,k)
! swap two arrays
 integer a1(k),a2(k),k,i,z
 do i=1,k
  z=a1(i); a1(i)=a2(i); a2(i)=z
 end do
end 

program test
 implicit none
 integer a(100,100),n,m,i,j
 real r(100,100)
 n=100;m=100
 call random_number(r) 
 a=r*100

 call printArr(a,6,3)
 call full_sort(a,n,m)
 call printArr(a,6,3)
end 

subroutine printArr(a,n,m)
 integer a(n,m),n,m,i,j
 do i=1,n
  print * ,(a(i,j),j=1,m)
 end do
end 

________________________________________________________________________________

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

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

integer ::a(10)=(/-5,4,6,-1,-2,5,1,13,-56,-11/),b(10),i,k,n
n=10
print *,a

k=0
do i=1,n
 if (a(i)<0) then
   k=k+1
   b(k)=a(i)
 end if  
end do
do i=1,n
 if (a(i)>=0) then
   k=k+1
   b(k)=a(i)
 end if  
end do
print *,b
end 

integer ::a(10)=(/-5,4,6,-1,-2,5,1,13,-56,-11/),b(10),i,k,j,n
n=10
print *,a
k=0
j=n
do i=1,n
 if (a(i)<0) then
   k=k+1
   b(k)=a(i)
 else
   b(j)=a(i)
   j=j-1
 end if  
end do
print *,b
end 

1. ищем положительный элемент слева,
2. ищем отрицательный элемент справа,
3. переставляем их местами.

program FTEST 
implicit none 
integer a(10),i,j,state1,n 
a=(/-5,1,4,-6,7,-4,3,5,-6,7/) 
n=10 
state1=0; 
print *,a 

i=1; j=n 
do 
 if (state1==0) then 
	 if (a(i)>=0) then 
 		state1=1 
	else 
		i=i+1 
	end if 
 end if 
 if (state1==1) then 
 	if (a(j)<0) then 
		call swap(a(i),a(j)) 
		state1=0 
	else 
		j=j-1 
	end if 
 end if 
 if (i==j) exit 
end do 

print *,a 
end program FTEST 

subroutine swap(i,j) 
integer i,j,k 
k=i; i=j; j=k 
end 

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

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

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

________________________________________________________________________________

Программа должна находить факториалы первых 12 чисел (рекурсивный вариант).

Так как надо повторять вычисления факториала 12 раз, воспользуемся циклом со счетчиком:

do i=1,12
 вычислить и распечатать факториал i!
end do 

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

 
  INTEGER FACTORIAL
  DO N=1,12
      WRITE (6,*) N,' factorial is ',FACTORIAL(N)
  END DO
  END
  

Факториал некоторого числа N равен 1*2*3*...*N. Его также можно представить в виде N!=(N-1)!*N. Если бы мы могли найти (N-1)!, мы бы вычислили результат. Но, в свою очередь, (N-1)!=(N-2)! *(N-1). Так мы дойдем до 3!=2!*3. А 2!==2 - дальше идти не нужно.

N!->(N-1)! ->(N-2)!->.....
     *	          *
     N            N-1

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

FACTORIAL = FACTORIAL(N-1) * N

(1) RECURSIVE FUNCTION FACTORIAL (N) RESULT(fct)
(2)  INTEGER fct,N
(3)	 print *,'n=',N
(4)	 IF (N > 2) THEN
(5)		FCT = FACTORIAL(N-1) * N
(6)	 ELSE
(7)		FCT= N
(8)	 END IF
(9) 	 print *,N,Fct
(10) END
! main program для отладки вычисляет факториал 5
PROGRAM FACTORIAL_TEST
	INTEGER FACTORIAL
    WRITE (6,*) 5,' factorial is ',FACTORIAL(5)
END

		   
n=           5
n=           4
n=           3
n=           2
           2           2
           3           6
           4          24
           5         120
           5  factorial is          120

          2           2 

          3           6

          5  factorial is          120

! main program вычисляет факториал 12 чисел
PROGRAM FACTORIAL_TEST
	INTEGER FACTORIAL,i
	do i=1,12
	    WRITE (6,*) i,' factorial is ',FACTORIAL(i)
	end do
END

RECURSIVE FUNCTION FACTORIAL (N) RESULT(fct)
 INTEGER fct,N
  IF (N > 2) THEN
	FCT = FACTORIAL(N-1) * N
 ELSE
	FCT= N
 END IF
END

________________________________________________________________________________

Нахождение минимального элемента в массиве (рекурсивный вариант).

recursive function Min_a_r(ar,n) result(res)
implicit none
integer ar(n),n,res,mn
	 if (n==2) then
    	res=min(ar(1),ar(2))
 	else
    	mn=Min_a_r(ar(2:n),n-1)	! превый параметр - сечение массива без первого элемента
    	res=min(ar(1),mn)
 	end if
end

implicit none
real fr(10)
integer :: ar(10)=(/12,2,13,4,52,6,17,8,9,20/),Min_a_r
call random_number(fr)
ar=fr*100
print *,ar
print *,Min_a_r(ar,10)
end 

________________________________________________________________________________

Программа должна вывести адрес числа в массиве с помощью дихотомии (рекурсивный вариант).

recursive function dixotom(ar,a,b,c) result(res)
implicit none
! ar() - исходный массив
! a,b  - границы отрезка
! с - искомый элемент
! ! нет проверки на наличие элемента

 integer ar(*),a,b,c,res,k
 k=(a+b)/2.
 if (ar(k)==c) then
   res=k
   return
 end if
 if (ar(k)>c) then
  res=dixotom(ar,a,k,c)
 else 
  res=dixotom(ar,k,b,c)
 end if
end

integer dixotom
integer :: ar(10)=(/1,2,3,4,5,6,7,8,9,10/)
print *,dixotom(ar,1,10,3) ! поиск 3 в исходном массиве
end 

________________________________________________________________________________

Вычисление квадратного корня (рекурсивный вариант)

	
recursive function sqrt_r(x,y,eps) result (res)
real x,y,eps,res
print *,x,y
 if (abs(y/x-x)< eps) then 
   res=x
 else

   res=sqrt_r((x+y/x)/2.,y,eps)
 end if
end


real sqrt_r,y,eps
print *,'введите число и точность'
read *,y,eps
print*,sqrt_r((y+1.)/2.,y,eps)	! (y+1.)/2. - начальное приближение
end 

Нерекурсивный вариант этой задачи смотри выше.

________________________________________________________________________________

Нахождение наибольшего общего делителя двух чисел.

Наибольшим общим делителем двух целых чисел р и q называется наибольшее целое число d, которое делит р на q нацело.

Эта задача имеет много решений. Первое, которое приходит на ум - тривиальное - простым перебором:  

function NODtr(a,b)
! тривиальная версия 
implicit none
integer a,b,NODtr
integer i
do i=min(a,b)/2,2,-1
 if (mod(a,i)==0 .and. mod(b,i)==0) then
  NODtr=i
  return
 end if
end do
 NODtr=1
end 

Так как нужно найти наибольший делитель, начинаем с максимально большого делителя - min(a,b)/2. Далее в цикле уменьшаем делитель и ищем то значение, на которое одновременно делятся оба числа. Цикл заканчивается на числе2.

Если в цикле не нашли общего делителя, возвращаем "универсальный делитель" - 1.

Но можно воспользоваться более быстрым алгоритмом: Пусть r- остаток от деления р на q.
Если r равно 0, то q является наибольшим общим делителем. В противном случае пусть p равно q, затем — q равным r и повторить процесс нахождения остатка от деления р на q.

Эта задача имеет красивое рекурсивное решение:

recursive function NODr(a,b) result (res)
! рекурсивное вычисление НОД
implicit none
integer res,a,b
print *,'r-',a,b
if (b>a) then
  res=NODr(b,a)
else if(b==0) then
  res=a
else
  res=NODr(b,mod(a,b))
end if
end

function NOD(pa,pb) 
! вычисление НОД
implicit none
integer pa,pb,NOD
integer a,b,c
! чтобы избежать их изменения, запомним значения параметров в локальных переменных 
a=pa; b=pb; 

do 
print *,'--',a,b
 if(b==0) then
   NOD=a
   return
 else if (a>b) then
   a=mod(a,b)
 else
   c=a; a=b; b=c;
 end if
end do
end

function NOD1(pa,pb) 
! вычисление НОД
implicit none
integer pa,pb,NOD1
integer a,b,c
 if (a>b) then
  a=pa; b=pa;
 else
  a=pb; b=pa;
 end if
 do 
  print *,'!-',a,b
  if(b==0) then
   NOD1=a
   return
  else
   c=a
   b=mod(a,b)
   a=c
  end if
 end do
end

program NOD_test
integer a,b,r1,r2,r3,r4
print *,'enter a,b'
read *,a,b
  r1=NODr(a,b)
  r2=NOD(a,b)
  r3=NOD1(a,b)
  r4=NODtr(a,b)
  print *,r1,r2,r3,r4
end

________________________________________________________________________________

Задачи для домашних проработок:

1. Дано натуральное (целое неотрицательное) число а и целое положительное число d. Вычислить частное q и остаток r при делении а на d, не используя операций div и mod.
2. Составить программу, печатающую квадраты всех натуральных чисел от 0 до заданного натурального n.
3. Составить программу, печатающую разложение на простые множители заданного натурального числа n > 0.
4. Надо напечатать десятичную запись введенного числа в обратном порядке. (Для n = 173 надо напечатать 371.)
5. Дано натуральное n. Подсчитать количество решений неравенства x*x + y*y < n в натуральных (неотрицательных целых) числах, не используя действий с вещественными числами.
6. (Э. Дейкстра). Функция f с натуральными аргументами и значениями определена так: f(0) = 0, f(1) = 1, f (2n) = f(n), f (2n+1) = f (n) + f (n+1). Составить программу вычисления f (n) по заданному n.
7. Дан массив x из n целых чисел, причём x[1] <= x[2] <= ... <= x[n]. Найти количество различных чисел среди элементов этого массива.
8. Дан массив x [1]..x[n] целых чисел. Не используя других массивов, переставить элементы массива в обратном порядке.
9. Даны два возрастающих массива целых чисел x и y. Найти количество общих элементов в этих массивах (т. е. количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j). (Число действий порядка k+l.)
10. Даны два массива x[1] <= ... <= x[k] и y[1] <= ... <= y[l]. "Соединить" их в массив z[1] <= ... <= z[m] (m = k+l; каждый элемент должен входить в массив z столько раз, сколько раз он входит в общей сложности в массивы x и y). Число действий порядка m.
11. (Двоичный поиск) Дана последовательность x[1] <= ... <= x[n] целых чисел и число a. Выяснить, содержится ли a в этой последовательности, т. е. существует ли i из 1..n, для ко- торого x[i]=a. (Количество действий порядка log
12. (из книги Д.Гриса) Дана последовательность целых чисел x[1],..., x[n]. Найти максимальную длину ее возрастающей подпоследовательности (число действий порядка n*log(n)).
13. Осуществить циклический сдвиг одномерного массива из N элементов на I позиций.
14. Дан одномерный массив случайно расположенных N чисел. Найти одно пропущенное число.
15. В файле записан текст. Переписать все слова текста, содержащие наиболее часто встречающуюся в тексте букву, в другой файл, и найти самое длинное из них.

/* mirror the input number */
#include 

void main()
{
	char str[255],*sm;
	int mlt,p;
    puts("enter srting");
	gets(str);
	
	for(sm=str,mlt=1,p=0;*sm;sm++,mlt*=10) p+=((*sm-'0')*mlt);
	
	printf("%d \n",p);
}