Тема:Одномерные массивы Дан список 10 магазинов и соответствующий ему список цен на учебники. Отсортировать список магазинов по возрастанию цен. Вывести на экран отсортированный список. Подсчитать и вывести на экран количество магазинов с самыми дешевыми учебниками. Вывести на экран названия магазинов, где учебники дешевле всего.
Ответы
Учитывая, что 50 - это очень немного (50-е простое число всего лишь 229), можно придумать всё что угодно (даже ужасающе неэффективное).
Можно просто перебирать все числа, начиная с двойки, и каждое делить на все меньшие его, начиная с двойки. Если хоть на одно разделится - не простое, иначе простое. Попутно подсчитывая число простых чисел, N-е найти не составит труда.
Псевдокод:
ввод N
i = 2
counter = 0
нц
для j = 2..(i - 1)
если i mod j = 0 тогда
увеличить i на 1
следующая итерация внешнего цикла
увеличить counter на 1
если counter = N тогда
вывод i
завершение работы программы
увеличить i на 1
кц
Дальше можно изменять эту программу, оптимизировать. Например, известно, что меньший собственный делитель любого составного числа не превосходит корня из этого числа, следовательно, можно во внутреннем цикле делать перебор не до i - 1, а до [sqrt(i)].
Другое полезное наблюдение может заключаться в том, что все простые числа кроме 2 имеют вид 6m - 1 или 6m + 1 (остальные не подходят: очевидно, 6n делится на 6, 6n +-2 четные числа, а 6n + 3 делится на 3). Это наблюдение позволит примерно в три раза сократить число итераций внешнего цикла.
Наконец, можно сохранять все встретившиеся простые числа в массив, и затем проверять, делится ли текущее число на простые числа, меньшие себя: если не делится, то оно - тоже простое. Для хранения 50 маленьких натуральных чисел в памяти не нужно много места.
Можно воспользоваться каким-нибудь другим алгоритмом, например, решетом Эратосфена. Но в зависимости от того, на каком языке программирования будет потом реализовываться этот алгоритм, он может записываться нетривиально. Для выполнения "на бумажке" решето Эратосфена - один из самых удобных
В конце концов, можно использовать "читерский" метод - взять откуда-нибудь первые 50 простых чисел, записать их куда-нибудь, а потом просто за O(1) находить нужное число в памяти.
Можно просто перебирать все числа, начиная с двойки, и каждое делить на все меньшие его, начиная с двойки. Если хоть на одно разделится - не простое, иначе простое. Попутно подсчитывая число простых чисел, N-е найти не составит труда.
Псевдокод:
ввод N
i = 2
counter = 0
нц
для j = 2..(i - 1)
если i mod j = 0 тогда
увеличить i на 1
следующая итерация внешнего цикла
увеличить counter на 1
если counter = N тогда
вывод i
завершение работы программы
увеличить i на 1
кц
Дальше можно изменять эту программу, оптимизировать. Например, известно, что меньший собственный делитель любого составного числа не превосходит корня из этого числа, следовательно, можно во внутреннем цикле делать перебор не до i - 1, а до [sqrt(i)].
Другое полезное наблюдение может заключаться в том, что все простые числа кроме 2 имеют вид 6m - 1 или 6m + 1 (остальные не подходят: очевидно, 6n делится на 6, 6n +-2 четные числа, а 6n + 3 делится на 3). Это наблюдение позволит примерно в три раза сократить число итераций внешнего цикла.
Наконец, можно сохранять все встретившиеся простые числа в массив, и затем проверять, делится ли текущее число на простые числа, меньшие себя: если не делится, то оно - тоже простое. Для хранения 50 маленьких натуральных чисел в памяти не нужно много места.
Можно воспользоваться каким-нибудь другим алгоритмом, например, решетом Эратосфена. Но в зависимости от того, на каком языке программирования будет потом реализовываться этот алгоритм, он может записываться нетривиально. Для выполнения "на бумажке" решето Эратосфена - один из самых удобных
В конце концов, можно использовать "читерский" метод - взять откуда-нибудь первые 50 простых чисел, записать их куда-нибудь, а потом просто за O(1) находить нужное число в памяти.
Ответить на вопрос
Поделитесь своими знаниями, ответьте на вопрос:
Популярные вопросы в разделе
Знатоки информатики нужно в каждом поставить верно или неверно
Автор: frolevgevg6420
Заполните пропущенные параметры для тегов фрагмента HTML-документа.
Автор: Михайлович_гергиевич315
Векторлық суреттердың сипаттары
Автор: Aleksandr740
<html>
<head>
<meta charset="utf-8">
<title>Задание</title>
<style type="text/css">
TABLE {
width: 400px; /* Ширина таблицы */
height: 500px; /* Высота таблицы */
border: 3px solid #2e8b57; /* Рамка вокруг таблицы */
}
TD, TH {
padding: 3px; /* Поля вокруг содержимого ячеек */
text-align: center; /* Выравнивание по центру */
}
.lc {
font-weight: bold; /* Жирное начертание текста */
text-align: left; /* Выравнивание по левому краю */
}
</style>
</head>
<body>
<table border="1">
<caption>Расписание</caption>
<tr>
<td>Номер урока</td>
<td>Название урока</td>
<td>Номер кабинета</td>
<td>Преподаватель</td>
</tr>
<tr>
<td></td><td></td><td></td><td></td>
</tr>
<tr><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td></tr>
<tr><td></td><td></td><td></td><td></td></tr>
</table>
</body>
</html>
Объяснение:
Частичные пояснения есть в коде.