Решение простой задачи?

← →
Vrangel (2007-08-17 14:52) [0]

Навеяно веткой про сумму ряда.
Задача:

С клавиатуры вводится число N большее нуля. Необходимо посчитать и вывести на экран сумму 1+2+3+...+(N-1)+N.

Как думаете, много ли школьников изучающих программирование в школе решат данную задачу с помощью цикла?

← →
@!!ex © (2007-08-17 14:55) [1]

Да. Очень многие могут решить такую задачу в школе с помощью цикла.
Практически все кто ездят на олимпиады такое могут решить.

← →
umbra © (2007-08-17 14:56) [2]

> простой

это не простая задача

← →
Юрий Зотов © (2007-08-17 15:06) [3]

> Vrangel (17.08.07 14:52)

Думаю, что многие смогут. Вопрос лишь в том, сколько итераций будет иметь этот цикл - N, N div 2, или еще сколько-то.

← →
ari_9 (2007-08-17 15:06) [4]

вопрос в том, что школьник выберет цикл а нешкольник напишет сразу в ответ (N+1)*N/2 ?

думаю и среди профессионалов многие бы не забивая голову воткнули бы цикл

← →
ari_9 (2007-08-17 15:08) [5]

← →
Jeer © (2007-08-17 15:08) [6]

> Решение простой задачи?

Это не наш, это америкосный метод.

Наш: s = 0.5*n*(n+1)

← →
DrPass © (2007-08-17 15:10) [7]

> что школьник выберет цикл а нешкольник напишет сразу в ответ

Вряд ли. Только если эту формулу они в свое время проходили и он ее помнит наизусть. Т.к. "сходу" выводить теоремы далеко не каждый профессиональный математик способен, а не школьник

← →
Jeer © (2007-08-17 15:14) [8]

> далеко не каждый профессиональный математик

Профессиональный математик знает, что такое ряды чисел и большинство вытекающих из них принципов, а также под рукой у него всегда "краткий" справичник, если мозг очень уж утомлен.

← →
Romkin © (2007-08-17 15:30) [9]

DrPass © (17.08.07 15:10) [7] Фигня. Эту формулу обычный инженер должен выводить мгновенно. Школьник тоже, поскольку должен еще ее помнить :)))

← →
Romkin © (2007-08-17 15:40) [10]

А вот, помниться, давненько я приводил задачу про телефонные номера, вот для нее действительно программист нужен.
Немного перефразирую: есть текстовый файл с семизначными телефонными номерами, по одному в строке, ряд цифр. Номера - почти все. Разумеется, лидирующих нулей нет.
Задача: написать программу, принимающую на вход этот файл и формирующую текстовый файл с перечислением номеров, которых нет в исходном.
Критерий: как можно быстрее, как можно меньше памяти использовать.
Помнится, похожую задачу первым решил McSimm :)
PS. Кто знает ответ - плиз, не торопиться. Дайте развлечься другим.

← →
iXT © (2007-08-17 15:43) [11]

При условии что N > 0 Еще не следует, что оно целое.

=> Условий для решения недостаточно, ИМХО.

+ Нет условий на ограничение числа, ибо N может быть 2^255-1, см[2]

← →
ari_9 (2007-08-17 15:51) [12]

iXT

какая разница, целое N или нет ?

← →
umbra © (2007-08-17 15:54) [13]

можно считать список чисел отсортированным?

← →
iXT © (2007-08-17 15:56) [14]

> [12] ari_9 (17.08.07 15:51)

Пусть n=5.5 Как должна будет работать программа? И какой ряд анализировать.

З.Ы. Разница не в N, а в условии :)

← →
Romkin © (2007-08-17 15:56) [15]

umbra © (17.08.07 15:54) [13] Конечно нет :)
Более того: номера могут дублироваться :-Р
В общем, почти все числа от 1000000 до 9999999 в беспорядке с дубликатами. Получить те, которых нет.

← →
iXT © (2007-08-17 15:57) [16]

> [13] umbra © (17.08.07 15:54)

Думаю что нет.

← →
Romkin © (2007-08-17 15:58) [17]

Исходный вариант этой задачи, кстати - вывести отсортированный список этих номеров без повторений ;)

← →
ari_9 (2007-08-17 15:58) [18]

umbra

если отсортирован, задача простая. просто двигаться по файлу, прибавляя к текущему числу 1, если следующая строка такая, то шаг вперед, нет - пишем в файл результтата

← →
ferr © (2007-08-17 16:01) [19]

array[1..7]

← →
ari_9 (2007-08-17 16:03) [20]

iXT

а, ну да. но там тогда ряд в середине "не сойдется", так как снизу идут числа 1, 2... а сверху 5.5, 4,5...

← →
ferr © (2007-08-17 16:04) [21]

ой, array[1..9] т.е., ну короче понятно =)

← →
Romkin © (2007-08-17 16:04) [22]

ferr © (17.08.07 16:04) [21] Это ты к чему?

← →
ferr © (2007-08-17 16:05) [23]

тороплюсь очень, извиняйте за обилие сообщений, но думаю надо считать сколько раз какая цифра на какой позиции попадалась. т.е. O(1) памяти O(n) времени.

P.S. задачу вижу первый раз.

← →
iXT © (2007-08-17 16:06) [24]

> [17] Romkin © (17.08.07 15:58)

Цикл от первого до последнего
сравнивать вверх до тех пор пока следующая вверх <= выбранной, (если: < то перетасчтить; = то удалить)

Но мне он не очень нравиться, наверняка дело в математике.

← →
iXT © (2007-08-17 16:10) [25]

> [24] iXT © (17.08.07 16:06)

Сравнивать можно тоже не тупо вверх, а изходя из значения выбранного, т.к. выше выбранного они отсортированы

← →
Romkin © (2007-08-17 16:12) [26]

iXT © (17.08.07 16:06) [24] Ничего не понял. Повторяю, список не отсортирован. Или ты хочешь в текстовом файле что-то перетаскивать?
ferr © (17.08.07 16:05) [23] Торопишься.
Я ожидаю хотя бы наметков алгоритма, ну или текста простенькой утилиты командной строки, без всяких классов внутри, кстати. Они не нужны :)

← →
Lacmus © (2007-08-17 16:14) [27]

>Romkin

TBits ?

← →
Romkin © (2007-08-17 16:21) [28]

Lacmus © (17.08.07 16:14) [27] А без него сможешь? :)

Можно записать в памяти 9999999 единичных битов и по мере чтения из файла номеров обнулять бит с прочитанным номером. Когда файл кончится, напичатать номера единичных битов.

Не перевелись еще программисты :)
Впрочем, тут еще надо уметь обращаться с единичным битом...

> palva © (17.08.07 16:24) [29]
> напичатать

напечатать. Блин, никогда раньше такого не было. Надо завязывать с интернетом.

← →
Algol (2007-08-17 16:35) [32]

> Не перевелись еще программисты :)
> Впрочем, тут еще надо уметь обращаться с единичным битом.
> ..

Хм...типичная задача с хеш-таблицей... Это экзотика ?

Lacmus © (17.08.07 16:41) [34] :)
Легко и без них, если знаешь о двоичных or и and

> Хм...типичная задача с хеш-таблицей... Это экзотика ?

Хеширование в один бит. Самое трудное - догадаться. Но реализация у начинающего программиста тоже вызовет трудности.
О чем говорить, если на простейший вопрос (от Юрия Зотова):
Чему будет равно W после выполнения следующего кода процессором Intel x86? Ответ объяснить. type PWord = ^word; var I: integer; W: word; begin I := High(I) shr 8; W := PWord(Integer(@I) + 2)^; end;
навскидку, без компьютера, не отвечает на собеседовании практически никто? :(

Я бы не ответил на вопрос...
По идее 0...
Хотя я не очень хорошо понимаю...

> навскидку, без компьютера, не отвечает на собеседовании практически никто? :(
Я тоже не могу ответить. Даже подумав.

>Romkin © (17.08.07 16:49) [35]
>навскидку, без компьютера, не отвечает на собеседовании практически никто? :(

Ошибка в одном бите ?

Вот и я о чем. Вот еще задача:
быстренько пару строк, есть переменная a: byte, установить у нее 5-й бит (младший бит - №0). Есть переменная b: byte, сбросить у нее 6-й бит.

Решение простой задачи? Найти похожие ветки