Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TA_last_u3.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆
  1. Приклади Послідовний пошук

Задана функція перевіряє, чи знаходиться число v серед елементів масиву а[l], а[l+1], ..., а[r] шляхом послідовного порівняння з кожним елементом, починаючи з початку. Якщо по досягненні останнього елемента потрібне значення не знайдене, то функція повертає значення -1. Інакше вона повертає індекс елемента масиву, що містить шукане число.

int search (int a[], int v, int 1, int r)

{

for (int i = 1; i <= r; i++)

if (v == a[i]) return i;

return -1;

}

Лема. Послідовний пошук досліджує N чисел при кожному неуспішному пошуку й в середньому порядку N/2 чисел при кожному успішному пошуку.

Дійсно, якщо кожне число в таблиці з рівною імовірністю може бути об'єктом пошуку, тоді (1 +2 + ... + N)/ N = (N+1)/2 є середньою ціною пошуку.

Структури даних. Масиви Решето Ератосфена

Ціль програми полягає в присвоєнні елементам a[i] значення 1, якщо i просте число, і значення 0 у протилежному випадку. Спочатку значення 1 привласнюється всім елементам масиву. Потім привласнюється значення 0 елементам, індекси яких не є простими числами (являють собою добуток відомих простих чисел). Якщо після цього деякий елемент a[i] зберігає значення 1, його індекс є простим числом.

Оскільки масив складається з елементів найпростішого типу, що приймають значення 0 або 1, для економії простору має сенс явно описати масив біт замість масиву цілих чисел. Крім того, у деяких середовищах програмування потрібно, щоб масив був глобальним, якщо значення N велике, або можна виділяти простір для масиву динамічно.

#include <iostream.h>

static const int N = 1000;

int main()

{int i, a [N];

for (i = 2; i < N; i++) a[i] = 1;

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

if (a[i])

for (int j = i; j*i < N; j++) a[i*j] = 0;

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

if (a[i])

cout << " " << i; cout << endl;

Обчислення найближчої точки

Ця програма демонструє використання масиву структур і представляє типовий випадок, коли елементи зберігаються в масиві для наступної обробки в процесі деяких обчислень. Підраховується кількість пар з N згенерованих випадковим образом точок на площині, що з'єднуються прямою, довжина якої менше за d. Час виконання складає O(N2), тому програма не може застосовуватися для великих значень N.

#include <iostream.h>

#include <stdlib.h>

#include "Point.h"

float randFloat()

{ return 1.0*rand()/RAND_MAX; }

int main(int argc, char *argv[])

{ float d = atof(argv[2]);

int i, cnt = 0, N = atoi (argv[l]);

point *a = new point [N];

for (i = 0; i < N; i++)

{

a[i].x = randFloat(); a[i].y = randFloat();

}

for (i = 0; i < N; i++)

for (int j = i+1; j < N; j++)

if (distance (a[i], a[j]) < d) cnt++;

cout << cnt << " pairs within " << d << endl;

}

Структури даних. Списки Приклад циклічного списку (задача Йосипа)

Для представлення людей, розставлених у коло, побудуємо циклічний зв'язний список, де кожен елемент (людина) містить посилання на сусідній елемент проти ходу годинникової стрілки. Ціле число i представляє i-ту людину в колі. Після створення циклічного списку з одного вузла уставляються вузли від 2 до N. У результаті утвориться окружність з вузлами від 1 до N. При цьому змінна х указує на N. Потім пропускаємо М-1 вузлів, починаючи з 1-го, і встановлюємо значення посилання (М-1)-го вузла таким чином, щоб пропустити М-ий вузол. Продовжуємо цю операцію, поки не залишиться один вузол.

#include <iostream.h>

#include <stdlib.h>

struct node

{ int item; node* next;

node(int x, node* t)

{ item = x; next = t;}

typedef node *link;

int main(int argc, char *argv[])

{ int i, N = atoi(argv[l]) , M = atoi(argv[2]);

link t = new node(1, 0); t->next = t;

link x = t;

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

x = (x->next = new node(i, t)) ;

while (x != x->next)

{

for (i = 1; i < M; x->next) x = x->next;

x->next = x->next->next;

}

cout << x->item << endl;

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]