Билет № 12. Написать программу на поиск элементов массива по заданному условию

Pascal

QBasic

Pascal

QBasic

Написать программу на поиск элементов массива по заданному условию. Произвести ввод и отладку программы. Проанализировать полученный результат

Пример 1. В произвольном линейном массиве найти первый по порядку элемент, равный заданному числу x.

Решение. Просматриваем массив до тех пор, пока не будет найден указанный элемент или не будет просмотрен весь массив.

DECLARE SUB Vvod (N!, A!())

DECLARE SUB Vivod (N!, A!())

DECLARE SUB poisk (N!, A!(), x, p!)

DIM A(20), N, x AS INTEGER

RANDOMIZE TIMER - 32767

PRINT "N? ": INPUT N

CALL Vvod(N, A())

CALL Vivod(N, A())

PRINT "Что ищем? ": INPUT x

CALL poisk(N, A(), x, p)

IF p = 0 THEN

PRINT "No"

ELSE

PRINT "Номер: "; p

END IF

SUB poisk (N, A(), x, p)

i = 1

p = 0

WHILE (i <= N) AND (p = 0)

IF A(i) = x THEN p = i

i = i + 1

WEND

END SUB

SUB Vivod (N, A())

FOR i = 1 TO N

PRINT USING "####"; A(i);

NEXT i

PRINT

END SUB

SUB Vvod (N, A())

FOR i = 1 TO N

A(i) = -10 + INT(RND(1) * 20)

NEXT i

END SUB

Program Find;

Type arr=array[1..20] of integer;

Procedure Vvod(n: byte; var a: arr);

Var i: byte;

Begin

For i:= 1 to n do

A[i]:= -10 + random(20)

End;

Procedure Vivod(n: byte; const a: arr);

Var i: byte;

Begin

For i:= 1 to n do

Write(a[i]:4);

Writeln

End;

Procedure poisk(n: byte; const a: arr; x: integer; var p: byte);

Var i: byte;

Begin

i:= 1; p:= 0;

while (i <= n) and (p = 0) do begin

if a[i] = x then p:= i;

i:= i + 1

end;

End;

Var a: arr; x: integer; n, p: byte;

Begin

Randomize;

Write('n?'); readln(n);

Vvod(n, a);

Vivod(n, a);

Write('Что ищем?'); readln(x);

Poisk(n, a, x, p);

If p = 0 then writeln('Элемент не найден')

else writeln('номер элемента: ', p)

End.

C++

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

void Vvod(int n, int a[20]);

void Vivod(int n, int a[20]);

void Poisk(int n, int a[20], int x, int &p);

void main()

{int n, a[20], x, p;

cout << "Сколько элементов в массиве? ";

cin >> n;

randomize();

Vvod(n, a);

Vivod(n, a);

cout << "Что ищем?";

cin >> x;

Poisk(n, a, x, p);

if (!p) cout << "Элемент не найден";

else cout << "номер элемента: " << p;

}

void Vvod(int n, int a[20])

{ int i;

for (i = 1; i <= n; i++)

a[i] = -10 + random(20);

}

void Vivod(int n, int a[20])

{ int i;

for (i = 1; i <= n; i++)

{cout.width(4); cout << a[i];}

}

void Poisk(int n, int a[20], int x, int &p)

{ int i;

p = 0;

for (i = 1; i <= n &&!p; i++)

if (a[i] == x) p = i;

}

Пример 2. В отсортированном линейном массиве найти элемент, равный заданному числу x.

Решение. Воспользуемся алгоритмом бинарного поиска. Для этого выделим средний элемент массива. По сравнению с x средний элемент может быть: больше x (в этом случае поиск продолжается в левой части массива); меньше x (в этом случае поиск продолжается в правой части массива); равен x (в этом случае поиск завершается). В первом и втором случае поиск продолжаем по той же схеме.

Кроме совпадения некоторого элемента массива с заданным x поиск прекращается, если левая граница участка поиска станет больше, чем правая, что означает, что элемент в массиве отсутствует.

DECLARE SUB Vvod (N!,A() AS INTEGER)

DECLARE SUB Vivod (N!,A() AS INTEGER)

DECLARE SUB Bpoisk (N!,A() AS INTEGER,x,p!)

DIM A(20) AS INTEGER

RANDOMIZE TIMER - 32767

PRINT "N? ": INPUT N

CALL Vvod(N, A())

CALL Vivod(N, A())

PRINT "Что ищем? ": INPUT x

CALL Bpoisk(N, A(), x, p)

IF p = 0 THEN

PRINT "No"

ELSE

PRINT "Номер: "; p

END IF

SUB Bpoisk (N, A() AS INTEGER, x, c)

L = 1: R = N

DO

c = INT((L + R) / 2)

IF A(c) > x THEN R = c - 1

IF A(c) < x THEN L = c + 1

LOOP WHILE (L <= R) AND (A(c) <> x)

IF A(c) <> x THEN c = 0

END SUB

SUB Vivod (N, A() AS INTEGER)

FOR i = 1 TO N

PRINT USING "####"; A(i);

NEXT i

PRINT

END SUB

SUB Vvod (N, A() AS INTEGER)

A(1) = -20 + INT(RND(1) * 20)

FOR i = 2 TO N

A(i) = A(i - 1) + INT(RND(1) * 6)

NEXT i

END SUB

Program Find;

Type arr = array[1..20] of integer;

Procedure Vvod(n: byte; var a: arr);

Var i: byte;

Begin

A[1]:= -20 + random(20);

For i:= 2 to n do

A[i]:= A[i - 1] + random(6)

End;

Procedure Vivod(n: byte; const a: arr);

Var i: byte;

Begin

For i:= 1 to n do

Write(a[i]:4);

Writeln

End;

Procedure bpoisk(n: byte; const a: arr;

x: integer; var C: byte);

Var L,R: byte;

Begin

L:= 1; R:= n;

Repeat

C:= (L + R) div 2;

If A[C] > x then R:= c - 1;

If A[C] < x then L:= c + 1

Until (L > R) or (A[c] = x)

If A[C] <> x then C:= 0

End;

Var a: arr; x: integer; n, p: byte;

Begin

Randomize;

Write('n? '); readln(n);

Vvod(n, a);

Vivod(n, a);

Write('Что ищем? '); readln(x);

BPoisk(n, a, x, p);

If p = 0 then

writeln('Элемент не найден') else

writeln('номер элемента: ', p)

End.

C++

#include <iostream.h>

#include <stdlib.h>

#include <time.h>

void Vvod(int n, int a[20]);

void Vivod(int n, int a[20]);

void BPoisk(int n, int a[20], int x, int &c);

void main()

{int n, a[20], x, p;

cout << "Сколько элементов в массиве? ";

cin >> n;

randomize();

Vvod(n, a);

Vivod(n, a);

cout << " Что ищем?";

cin >> x;

BPoisk(n, a, x, p);

if (!p) cout << "Элемент не найден";

else cout << "номер элемента: " << p;

}

void Vvod(int n, int a[20])

{ int i;

a[1] = -20 + random(20);

for (i = 2; i <= n; i++)

a[i] = a[i - 1] + 1 + random(6);

}

void Vivod(int n, int a[20])

{ int i;

for (i = 1; i <= n; i++)

{cout.width(4); cout << a[i];}

cout << endl;

}

void BPoisk(int n, int a[20], int x, int &c)

{ int L, R;

L = 1; R = n;

do

{c = (L + R)/2;

if (a[c] > x) R = c - 1;

if (a[c] < x) L = c + 1;}

while (L <= R && a[c]!= x);

if (a[c]!= x) c = 0;

}

Варианты заданий

Написать программу на поиск элементов массива по заданному условию. Произвести ввод и отладку программы. Проанализировать полученный результат.

1. Даны действительные числа a 1, a 2,..., an. Поменять местами наибольший и наименьший элементы.

2. Задана последовательность из N вещественных чисел. Определить, сколько чисел меньше K, равно K и больше K.

3. Определить количество элементов последовательности натуральных чисел, кратных числу M и заключенных в промежутке от L до N.

4. Определить, сколько процентов от всего количества элементов последовательности целых чисел составляют нечетные элементы.

5. В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если таких чисел несколько, то определить наименьшее из них.

Дата добавления: 2015-04-23