ПРИМЕРНАЯ ТЕМАТИКА КУРСОВЫХ РАБОТ
Темы согласовываются с преподавателем каф. информатики.
Постановка вычислительных задач.
1. Найти такую расстановку пяти ферзей на шахматной доске, при которой каждое поле находится под ударом одного из них. Один из вариантов расстановки представить на экране в графической форме.
2. Найти такую расстановку двенадцати коней на шахматной доске, при которой каждое поле находится под ударом одного из них. Один из вариантов расстановки представить на экране в графической форме.
3. Найти такую расстановку восьми слонов на шахматной доске, при которой каждое поле находится под ударом одного из них. Один из вариантов расстановки представить на экране в графической форме.
4. Дано натуральное число М. Получить М расстановок 8 ферзей на шахматной доске, при которой один ферзь не угрожает другому. Если М больше, чем число таких расстановок, то следует получить все расстановки.
5. Даны целые числа А(i),…,A(m). Определить, является ли эта последовательность периодической (т.е. может ли она быть получена повторениями некоторой своей начальной части). Из всех периодов указать наименьший.
6. Элемент матрицы называется седловой точкой, если он является одновременно наименьшим в свой строке и наибольшим в своем столбце или, наоборот, является наибольшим в своей строке и наименьшим в своем столбце. Дана действительная матрица размером 10´15. Выяснить, имеются ли седловые точки в этой матрице, и если имеются, указать индексы одной из них. Результат представить в графической форме на экране с выделением седловых точек.
7. «Задача о рюкзаке». Имеется М различных предметов, известны вес каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы общий вес не превышал заданной границы, а общая стоимость была максимальной. Решить эту задачу для М предметов, веса которых в килограммах равны Р1, Р2, …, Рм, стоимости - С1, С2, …, См. Вес рюкзака не должен превышать 50 килограммов.
8. Игра в слова. Программа выбирает слово и рисует на экране столько прочерков, сколько букв в этом слове. Отгадать, какое слово загадано программой. В каждый ход играющий указывает одну букву. Если названа буква, входящая в состав слова, она подставляется вместо соответствующего прочерка. В противном случае играющий теряет одно очко. В начальный момент у играющего 15 очков.
9. «Коровы и быки». Программа выбирает с помощью датчика случайных чисел четырехзначное число с разными цифрами. Угадать это число. На каждом шаге играющий называет четырехзначное число, а программа сообщает, сколько цифр числа угадано (быки) и сколько цифр угаданных стоит на нужном месте (коровы). Например, если программой загадано число 1294, а играющий назвал 1423, он получает ответ «одна корова, три быка».
10. «Подбери ключи». Перед играющим четыре запертые двери. Открыть все двери, располагая десятью ключами, каждый из которых может открыть несколько дверей. Представляется 14 попыток.
11. Составить программу для заучивания слов иностранного языка. Программа должна предлагать слово из некоторого списка на одном языке, обучающийся - дать перевод этого слова на другом языке.
12. Составить программу для тренировки памяти. Программа должна высветить на экран несколько точек, играющий - указать, в каком порядке эти точки были высвечены. Координаты точек выбираются в программе с помощью датчика случайных чисел.
13. Для заданной целочисленной матрицы найти максимум среди сумм элементов диагоналей, параллельных главной диагонали матрицы.
14. Подсчитать количество строк заданной целочисленной матрицы размером 20´20, являющихся перестановкой чисел 1, 2, …20.
15. В заданной последовательности целых чисел найти самую длинную под последовательность, которая является арифметической или геометрической прогрессией.
16. Построить последовательность длинной 100, образованную цифрами пятеричного представления последовательности натуральных чисел, начинающейся с заданного N.
17. Многоугольник (не обязательно выпуклый) задан на плоскости пересечением координат вершин в порядке обхода его границ. Определить площадь многоугольника. Решение задачи (с вычерчиванием самого многоугольника) представить в графическом виде на экране.
18. Задано множество точек М в трехмерном пространстве. Найти такую из них, где шар заданного радиуса с центром в этой точки содержит максимальное число точек из М.
19. На плоскости задано множество точек А и множество окружностей В. найти две такие различные точки из А, чтобы проходящая через них прямая пересекается с максимальным количеством окружностей из В.
Результат подтвердить графическим изображением на экране.
20. На плоскости задано множество точек А и множество прямых В. найти две такие различные точки из А, чтобы проходящая через них прямая параллельна наибольшему количеству прямых из В. результат представить в виде графического изображения на экране.
21. Дано 3*N точек на плоскости, причем никакие три из них не лежат на одной прямой. Построить множество N треугольников с вершинами в этих точках так, чтобы никакие два треугольника не пересекались и не содержали друг друга. Результат вывести на экран в графическом виде.
22. Из заданного множества точек на плоскости выбрать три разные точки А, В, С так, чтобы внутри треугольника АВС содержалось максимальное количество точек этого множества. Результат представить на экране в графическом виде.
23. Даны два множества точек на плоскости. Найти центр и радиус окружности, проходящей через K (K ³3) точек первого множества и содержащий строго внутри себя М точек второго множества. Результат вывести на экран в графическом виде.
24. Даны два множества точек на плоскости. Из первого множества выбрать три различные точки так, чтобы треугольник с вершинами в этих точках содержал (строго внутри себя) равное количество точек первого и второго множества. Подтвердить графическим изображением на экране.
25. Даны два множества точек на плоскости. Выбрать четыре различные точки первого множества так, чтобы четырех угольник с вершинами в этих точках накрывал все точки второго множества и имел минимальную площадь. Результат представить на экране в графическом виде.
26. Даны два множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы круг, ограниченный окружностью, проходящей через эти три точки, содержал все точки второго множества и имел минимальную площадь. Результат представить графическим изображением на экране.
27. На плоскости заданы множества точек и окружность радиусом R с центром в начале координат. Построить множество всех треугольников с вершинами в заданных точках, имеющих не пустое пересечение с окружностью, и вывести на экран в графическом виде.
28. Из заданного на плоскости множества точек выбрать три различные точки так, чтобы разность между площадью круга, ограниченного окружностью, проходящей через три точки, и площадью треугольника с вершинами в этих точках была минимальной. Результат представить в виде графического изображения на экране.
29. Найти минимальное множество прямых, на которых можно разместить все точки заданного на плоскости множества точек. Результат вывести на экран в графическом виде.
30. Найти минимальное множество окружностей, на которых можно разместить все точки заданного на плоскости множества точек.
Представить графическую интерпретацию решения задачи.
31. Построить N прямых таким образом, чтобы на каждой прямой лежали по крайне мере две различные точки заданного множества точек на плоскости, а количество треугольников, образуемых пересечением этих прямых, было максимальным. Представить графическое изображение результата решения задачи.
32. Имеется N костей из нескольких комплексов домино. Выстроить из них правильную последовательность максимальной длины. Формирование набора костей выполнить с помощью датчика случайных чисел.
33. Даны два различных слова, в каждом из которых от 1 до 8 строчных латинских букв и за каждым из которых - пробел. Напечатать эти слова в алфавитном порядке. (Считать, что литера «пробел» предшествует любой литере-букве).
34. Даны две литеры – латинская буква (от a до h) и цифра (от 1 до 8), например, a2 или g5. Рассматривая их координаты поля шахматной доски, на котором находится ферзь, нарисовать шахматную доску, пометив крестиками все поля, которые «бьёт» этот ферзь, и ноликами все остальные поля. Изображение вывеси на экран в графическом виде.
35. Дана последовательность, содержащая от 1 до 90 слов, в каждом из которых от 1 до 10 строчных русских букв; между соседними словами – не менее одного пробела, за последним словом – точка. Напечатать эти слова по алфавиту.
36. Построить два треугольника с вершинами в заданном множестве точек на плоскости так, чтобы первый треугольник лежал строго внутри второго. Представить результат в виде графического изображения на экране.
37. На плоскости задано множество окружностей. Две окружности А и В называются связанными, если они пересекаются, либо существует третья окружность С заданного множества, связанная с А и В. выбрать максимальное подмножество попарно не связанных друг с другом окружностей.
38. В старо-японском календаре принят 60-летний цикл, состоящий из пяти 12-летних подциклов. Подциклы обозначались названиями цвета: зелёный, красный, жёлтый, белый и черный. Внутри каждого подцикла годы носили названия животных: крысы, коровы, тигра, зайца, дракона, змеи, лошади, овцы, обезьяны, курицы, собаки, свиньи. (1984 год – год зелёной крысы – был началом очередного цикла).
39. Написать программу, которая вводит номер некоторого года нашей эры и выводит его название по старо японскому календарю на экране в поле соответствующего цвета.
40. Из двух городов А и В, удаленных друг от друга на 600 км, одновременно и навстречу выходят два поезда. Поезд, отправляющийся из города А, имеет скорость V1=40км/ч, скорость второго поезда V2=60км/ч. Одновременно из города А вылетает быстрая муха со скоростью V=200км/ч и летит навстречу поезду, отправившемуся из города В. При встрече с поездом муха разворачивается и летит в обратном направлении к поезду, идущему из пункта А. Когда она его встретит, то полетит в обратном направлении. Полет мухи продолжится до встречи поездов. Требуется составить алгоритм и программу для вычисления полного пути, который пролетит муха за Т отрезков пути. График движения поездов и мухи представить на экране в графической форме.
41. На плоскости заданы множество точек А и множество окружностей В. Найти две такие различные точки из А, что проходящая через них прямая пересекается с максимальным количеством окружностей из В. Решение задачи представить в виде графического изображения на экране дисплея.
42. На плоскости заданно множество точек А и множество прямых В. Найти две такие различные точки из А, что проходящая через них прямая параллельна наибольшему количеству прямых из В. Решение задачи представить в виде графического изображения на экране дисплея.
43. Выбрать три различных точки из заданного множества точек на плоскости так, что бы была минимальной разность между количеством точек, лежащих внутри и вне треугольника с вершинами в выбранных точек. Решение задачи представить в виде графического изображения на экране дисплея.
44. Найти кратчайший путь передвижения коня по шахматной доске, соединяющий два заданных поля доски.
45. Найти кратчайший путь передвижения ладьи по заданному клеточному полю, соединяющий две указанные его клетки.
46. Задано множество точек на плоскости. Выбрать из них четыре разных точки, которые являются вершинами квадрата наибольшего периметра.