последовательности
Блин, чувствую себя как-то не так на этом форуме: всё время спрашиваю и спрашиваю... Ну, да простят меня обыватели данного форума, ибо нелегко студентам учить программирование "с нуля"..
Ну да ладно, как говорил один человек - ближе к телу :) ..
Подкинул мне мой препод вот такую задачку для размышления:
дана последовательность из не менее чем двух натуральных чисел, за которой идёт нуль. Вычислить сумму тех из них, порядковые номера которых - простые числа. (прога должна давать ответ на промежутке чесел [0;12000])
Надеюсь на Вашу помошь:(
Ну да ладно, как говорил один человек - ближе к телу :) ..
Подкинул мне мой препод вот такую задачку для размышления:
дана последовательность из не менее чем двух натуральных чисел, за которой идёт нуль. Вычислить сумму тех из них, порядковые номера которых - простые числа. (прога должна давать ответ на промежутке чесел [0;12000])
Надеюсь на Вашу помошь:(
Знаешь, что такое простые числа?
1-й способ - делать тупо, отдельно проверять каждое число на простоту и складывать. При длинной полседовтельности работать будет долговато.
2-й способ - применить решето Эратосфена.
Пояснения нужны?
1-й способ - делать тупо, отдельно проверять каждое число на простоту и складывать. При длинной полседовтельности работать будет долговато.
2-й способ - применить решето Эратосфена.
Пояснения нужны?
[QUOTE=Cutty Sark]Знаешь, что такое простые числа?
1-й способ - делать тупо, отдельно проверять каждое число на простоту и складывать. При длинной полседовтельности работать будет долговато.
2-й способ - применить решето Эратосфена.
Пояснения нужны?[/QUOTE]
С простыми числами знаком. Про Эратосфена сегодня лекция была, ... дык всё равно чё-т не догоняю сути дела...:confused:
1-й способ - делать тупо, отдельно проверять каждое число на простоту и складывать. При длинной полседовтельности работать будет долговато.
2-й способ - применить решето Эратосфена.
Пояснения нужны?[/QUOTE]
С простыми числами знаком. Про Эратосфена сегодня лекция была, ... дык всё равно чё-т не догоняю сути дела...:confused:
У тебя есть последовательность
а1, а2, а3, ...., амного
Тебе надо найти а2+а3+а5+а7+...
Вся задача сводится к получению последовательности номеров 2,3,5,...
Берём массив Т такой же длины, что и исходный. Заполняем его единичками. Будем обозначать
Тк=2, если к - простое,
Тк=0, если к - составное,
Тк=1, если пока неизвестно (потому и единички изначально).
Т1 ставим 0 (хоть формально 1 не составное число, но нам оно не нужно).
Имеем
0 1 1 1 1 1 1 1 1 1 1 1 1 1
Дальше цикл
(Начало цикла)
Находим первую 1, заменяем её на 2, запоминаем её номер (2)
0 2 1 1 1 1 1 1 1 1 1 1 1 1
До конца последовательности заменяем все кратные этому номеру на 0
0 2 1 0 1 0 1 0 1 0 1 0 1 0
(Конец цикла)
Например, дальше:
Нашли 1-цу на позиции 3, заменили 1-цу на 2-ку:
0 2 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Обнулили каждое 3-е число:
0 2 2 0 1 0 1 0 0 0 1 0 1 0 0 0
И т.п.
В конце получишь последовательность с двойками на простых местах:
0 2 2 0 2 0 2 0 0 0 2 0 2 0 0 0 2 0
Осталось только просуммировать соответствующие элементы исходной последовательности. В принципе, это лучше даже делать сразу - по мере получения очередной двойки.
а1, а2, а3, ...., амного
Тебе надо найти а2+а3+а5+а7+...
Вся задача сводится к получению последовательности номеров 2,3,5,...
Берём массив Т такой же длины, что и исходный. Заполняем его единичками. Будем обозначать
Тк=2, если к - простое,
Тк=0, если к - составное,
Тк=1, если пока неизвестно (потому и единички изначально).
Т1 ставим 0 (хоть формально 1 не составное число, но нам оно не нужно).
Имеем
0 1 1 1 1 1 1 1 1 1 1 1 1 1
Дальше цикл
(Начало цикла)
Находим первую 1, заменяем её на 2, запоминаем её номер (2)
0 2 1 1 1 1 1 1 1 1 1 1 1 1
До конца последовательности заменяем все кратные этому номеру на 0
0 2 1 0 1 0 1 0 1 0 1 0 1 0
(Конец цикла)
Например, дальше:
Нашли 1-цу на позиции 3, заменили 1-цу на 2-ку:
0 2 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Обнулили каждое 3-е число:
0 2 2 0 1 0 1 0 0 0 1 0 1 0 0 0
И т.п.
В конце получишь последовательность с двойками на простых местах:
0 2 2 0 2 0 2 0 0 0 2 0 2 0 0 0 2 0
Осталось только просуммировать соответствующие элементы исходной последовательности. В принципе, это лучше даже делать сразу - по мере получения очередной двойки.
[COLOR=red]Большая просьба зайти на форум Студенты и ознакомиться с правилами постинга. Если вы еще раз назовёте тему подобным образом, буду вынуждена её удалить. [/COLOR]
Цитата:
У тебя есть последовательность
а1, а2, а3, ...., амного
Тебе надо найти а2+а3+а5+а7+...
а1, а2, а3, ...., амного
Тебе надо найти а2+а3+а5+а7+...
порядковый номер а1 = 1, а а2 = 2, по крайней мере в Паскале
[QUOTE=OlgaKr][COLOR=red]Большая просьба зайти на форум Студенты и ознакомиться с правилами постинга. Если вы еще раз назовёте тему подобным образом, буду вынуждена её удалить. [/COLOR][/QUOTE]
Как раз хотел товарищу об этом напомнить. ;)
Как раз хотел товарищу об этом напомнить. ;)
[QUOTE=OlgaKr]порядковый номер а1 = 1, а а2 = 2, по крайней мере в Паскале[/QUOTE]
Кажется, ты невнимательно прочитала либо условие, либо моё сообщение.
И вообще, это не совсем тема по Паскалю. С собственно Паскалем, как я понял, у товарища проблем нет.
Кажется, ты невнимательно прочитала либо условие, либо моё сообщение.
И вообще, это не совсем тема по Паскалю. С собственно Паскалем, как я понял, у товарища проблем нет.
вот глянь, то что приложил к сообщению. там почти как у тебя и с "решетом", можешь легко переделать под себя.
Цитата: Cutty Sark
Как раз хотел товарищу об этом напомнить. ;)
[FONT="Comic Sans MS"][SIZE="4"]Гм.. Совсем недавно тут обосновался, а народ уже товарищем называет :D [/SIZE][/FONT]
Цитата: sherry
[FONT=Comic Sans MS]Гм.. Совсем недавно тут обосновался, а народ уже товарищем называет :D [/FONT]
Вас уже просили не кричать на форуме, со слухом тут у всех в порядке, и созрением тоже. И не разводите флуд пожалуйста. Разговоры на подобные темы - в гостевой или через приват.
Всё-всё, понял. Теперь буду молчать, а говорить лишь изредка и очень-очень тихо: [SIZE="1"]вот так[/SIZE]:D
Цитата: sherry
..., а говорить лишь изредка и очень-очень тихо: [SIZE=1]вот так[/SIZE]:D
главное говорить по существу...