Лабораторная работа №1

Вид материала

Лабораторная работа

Содержание Лабораторная работа №3 Лабораторная работа №5 Лабораторная работа № 6 Лабораторная работа № 7 Лабораторная работа № 8 - 9 Лабораторная работа №10 Лабораторная работа № 16– 17

Подобный материал:

• Методические указания к лабораторным работам Лабораторная работа, 357.24kb.
• Лабораторная работа №3 кпк лабораторная работа №3 Тема: карманный персональный компьютер, 173.34kb.
• Методические возможности стенда Особенности работы на стендах уилс-1 Ознакомительное, 1487.3kb.
• Лабораторная работа по курсу «Физические основы микроэлектроники», 136.21kb.
• Лабораторная работа, 166.92kb.
• Самостоятельная работа по учебным пособиям, 471.48kb.
• Конспект урока в 9 классе по теме: «Магний», 84.54kb.
• Лабораторная работа №1 Введение в Windows. Работа с окнами и приложениями в Windows, 67.41kb.
• Знакомство c Excel, 1212.51kb.
• Лабораторная работа, 105.21kb.

Лабораторная работа №1

1. Дано натуральное число п. Найти количество цифр этого числа.
   
2. Дано натуральное число п. Найти сумму цифр этого числа.
   
3. Дано натуральное число п. Получить число, записанное теми же цифрами, переставленными в обратном порядке.
   
4. Палиндром – это сочетание символов, которые читаются одинаково туда и обратно.
   
   • Составить программу, которая определяет, является ли заданное число палиндромом.
     
   • Составить программу, которая определяет, является ли данная строка палиндромом.
     
5. Составить программу перевода натурального числа из десятичной системы счисления в двоичную.
   
6. Составить программу перевода числа из двоичной системы счисления в десятичную.
   

Лабораторная работа №3

1. Написать программу сложения двух «длинных» натуральных чисел.
   
2. Написать программу умножения «длинного» натурального числа на цифру.
   
3. Написать программу умножения «длинного» натурального числа на 10 в степени п. п=1, 2, 3, …
   
4. Используя в качестве подпрограмм, задачи 1 – 3, написать программу умножения двух «длинных» натуральных чисел.
   

Замечание: В задачах 1 – 3 «длинные» натуральные числа представить в виде одномерных массивов. Будем считать, что такое число имеет не более 100 цифр.

5. Вычислить:
   

А) 100! (факториал от числа 100);

В) 3²⁰⁰ (3 в двухсотой степени).

Лабораторная работа №5

Дан файл tel.txt, содержащий список из номеров телефонов (6 цифр) и фамилий. Используя метод хеширования с открытой адресацией, написать программу поиска записи по первым трем буквам фамилии.

В качестве хеш-функции использовать:

• сумму кодов символов по модулю т;
  
• сумму квадратов кодов символов по модулю т.
  

В качестве метода адресации использовать:

• линейный;
  
• квадратичный;
  
• двойное хеширование.
  

Попробовать все варианты и найти вариант с наименьшим количеством коллизии при создании хеш-таблицы. Определить зависимость коллизии от размера хеш-таблицы.

Лабораторная работа № 6

Дан текстовый файл tel.txt, состоящий из строк, каждая из которых содержит номер телефона (6 цифр) и фамилию, разделенное пробелом. Создать файл tel1.txt, отсортированный по столбцу «телефон», используя методы:

1. простых вставок;
   
2. простого выбора;
   
3. простых обменов (пузырьковая сортировка).
   

Оценить время выполнения сортировок.

Лабораторная работа № 7

Дан текстовый файл tel.txt, состоящий из строк, каждая из которых содержит номер телефона (6 цифр) и фамилию, разделенные пробелом. Создать файл tel1.txt, отсортированный по столбцу «телефон», используя:

4. сортировку слиянием;
   
5. быструю сортировку.
   

Оценить время выполнения сортировок.

Лабораторная работа № 8 - 9

Дан текстовый файл tel.txt, состоящий из строк, каждая из которых содержит номер телефона (6 цифр) и фамилию, разделенные пробелом. Создать файл tel1.txt, отсортированный по столбцу «телефон», используя:

1. пирамидальную сортировку;
   
2. сортировку подсчетом.
   

Оценить время выполнения сортировок.

Лабораторная работа №10

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

NewStack(S) – процедура «Создать пустой стек S» (или очистить стек);

EmptyStack(S): Boolean – логическая функция , которая равна True, если стек пустой;

InStack(S, x) – процедура «Добавит в конец стека S элемент х»;

OutStack(S, x) – процедура «Удалить из стека S последний элемент, присвоив его переменной х».

Задание: Дана строка, содержащая всевозможные комбинации скобок. Написать программу, которая проверяла, закрыты ли все скобки в этой строке.


Задание к лабораторной работе №11

Последовательность Хэмминга образует натуральные числа, не имеющие других простых делителей, кроме 2, 3 и 5. Найти:

• первые N элементов этой последовательности;
  
• суммы первых N элементов;
  
• N-й элемент по заданному номеру N;
  
• первый элемент, больший данного числа М, а также номер этого элемента в последовательности;
  
• суммы первых элементов с номера N по номер М.
  

Лабораторная работа №14– 15

1. а) Сгенерировать и вывести все перестановки чисел от 1 до п.
   

б) Задача коммивояжера. Есть п городов и задана матрица А[1..п, 1..п], которая содержит расстояние между всеми парами городов А_{i j} – расстояние от города i до города j.Найти замкнутый маршрут, проходящий через все города меньшей длины.

2. а) Написать программу, которая генерировала все размещения с повторениями при заданных п и k.
   

б) Задача о рюкзаке. Есть п предметов, каждый i предмет имеет массу и т_i и стоимость с_i. Есть рюкзак; максимальная масса предметов, которую он выдерживает, равна М. Надо уложить предметы в рюкзак так, чтобы сумма стоимости их была максимальной.

Лабораторная работа № 16– 17

1. Выход из лабиринта.
   

Лабиринт представляет собой прямоугольную таблицу M x N, в каждой клетке может быть препятствие # или проход. Необходимо найти выход из лабиринта до его границ.

Замечание: Используйте файл labirint.txt.

2. Задача о расстановке ферзей.
   

Расставить на шахматной доске 8 ферзей, чтобы они не били друг друга.

3. Игра в слова.
   

Дан список слов. Найти наиболее длинную последовательность слов, чтобы конец предыдущего совпадал с началом следующего.

Замечание: Используйте файл words.txt