Курс молодого бойца (читать

← →
Игорь Шевченко © (2004-12-26 00:55) [40]

Kerk © (25.12.04 12:07) [19]

> Нет, Игорь. Он должен это уметь.. И иконку в трей запуздырить
> и лоток выдвинуть.. задачи разные бывают.

Роман, а смысл долга уметь это делать ? Задач, которые требуют таких вот умений, очень ограниченное количество и они уже давным-давно решены, судя по обилию иконок в трее и "выдвигателей лотков CD-ROM" на разного рода download-сайтах. Я, к стыду своему, не знаю, кому может в здравом уме и твердой памяти придти в голову пользоваться программой, выдвигающей этот злополучный лоток, когда его можно выдвинуть кнопкой на самом устройстве. CD-ROM"ов без кнопок я за свою не очень короткую жизнь еще не видел, вряд ли чего-то пропустил.

С уважением,

← →
default © (2004-12-26 00:56) [41]

OneFragLeft © (26.12.04 00:49) [37]
туда же
может правда формулировка чуть другая в оригинале
"чем больше знаешь тем больше понимаешь что ничего не знаешь"

← →
Хакер © (2004-12-26 00:57) [42]

Игорь Шевченко © (26.12.04 0:55) [40]
ага, я ещё НЕ разу никогда не юзал спец-прогу для видвигания лотка :)))

← →
OneFragLeft © (2004-12-26 01:03) [43]

Вот тут возник ещё один вопрос:
А каких программ ещё нет? Кому что нужно?
Хочу начать делать то, что никто ещё не делал.
Чтобы возникали передо мной задачи, готовые
ответы на которые, нельзя найти.
Подкиньте идей. А то вроде есть программы для всего,
но программисты что-то ещё делают:)

← →
default © (2004-12-26 01:06) [44]

OneFragLeft © (26.12.04 01:03) [43]
попробуй для начала сделать [1]
несомненно неплохая алгоритмическая задача

← →
OneFragLeft © (2004-12-26 01:08) [45]

если честно, то я не понял что значит:
Основная проблема - сделать это за время O(N) с затратами памяти меньшими, чем O(N).
Поясните, пожалуйста.

← →
default © (2004-12-26 01:13) [46]

OneFragLeft © (26.12.04 01:08) [45]
линейный рост времени работы алгоритма как функции её числа
то есть к примеру на два элемента тратиться 4 секунды, на три элемента будет тратиться 6 секунд, на четыре 8 и тд
а используемая дополнительная память должна не зависеть от числа элементов либо расти по порядку медленне чем N
например, LogN*N

← →
OneFragLeft © (2004-12-26 01:16) [47]

Т.е. я могу создать ещё один такой-же массив?

← →
default © (2004-12-26 01:18) [48]

OneFragLeft © (26.12.04 01:16) [47]
тогда рост памяти будет линейно зависеть от числа элементов что не допускает условие
"с затратами памяти меньшими, чем
O(N)."

← →
OneFragLeft © (2004-12-26 01:20) [49]

ага, ясно.
Т.е. могу использовать только одну-две переменные?

← →
default © (2004-12-26 01:24) [50]

OneFragLeft © (26.12.04 01:20) [49]
да, какое-то ограниченное количество памяти либо память в зависимости от числа элементов массива должна расти медленне чем растёт линейная функция

← →
OneFragLeft © (2004-12-26 02:43) [51]

Вот так должно быть?

procedure ReOrder; var B,i,j,n:integer; S:Array[0..9] of Integer; begin i:=1;//счётчик n:=10;//кол-во элементов в массиве (просто не знаю как это программно посчитать) //ну а дальше ясно While i<round(n/2) do begin B:=S[i]; For j:=i to n-i do begin S[j]:=S[j+1]; end; S[n-i]:=B; i:=i+1; end;

Знаний маловато, поэтому не смог сделать чтобы в процедуру посылался массив.
Проверил на работоспособность с чётным и нечётным количеством элементов.
Вроде работает...

← →
default © (2004-12-26 02:58) [52]

OneFragLeft © (26.12.04 02:43) [51]
тут заведомо нелинейное время
лучше тогда не трогай её
на счёт решения - я сам его не знаю пока)

← →
OneFragLeft © (2004-12-26 03:14) [53]

А как узнать, существует ли оно вообще.
Может и нет решения.

← →
MBo © (2004-12-26 07:07) [54]

>OneFragLeft © (26.12.04 03:14) [53]
Решение существует.
Ограничения на размер памяти и время связаны вот с чем -
1. несложно создать второй такой же массив и скопировать нужные элементы на нужные места - т.е. это путь с большими затратами памяти.
2. Возможно многократно сложным образом переставлять элементы в исходном массиве, пока не придем к нужному порядку - это требует существенно более, чем n^2 операций - т.е. путь с большими затратами памяти.

Так вот задача состоит в том, чтобы использовать только несколько дополнительных переменных, и минимизировать число операций (перестановок). Задача любопытна, в частности, тем, что, поразмыслив, находишь решение для конкретного N, но оно может не работать для других размеров массива.

OneFragLeft © (25.12.04 2:07)

>все типичные задачи,
>которые должен уметь выполнять начинающий
> программист, осваивающий Delphi

- читать хорошие книги о Delphi
- пользоваться F1, MSDN, DelphiWorld, Google, VCL sources
- пробовать все на практике
- хорошенько поискать ответ на вопрос прежде чем постить на форумы

Все это должен уметь не только начинающий, но начинающему этого пока достаточно.

Игорь Шевченко © (25.12.04 2:16) [3]
Ну ты меня успокоил. :-)

MBo © (26.12.04 7:07) [54]
Я вот не понял как формируется новый массив:
- последнее, предпоследнее слева от него, предпредпоследнее справа ...
или
- первое слева, второе справа, третье слева за первым, четвертое - справа за вторым
?

>как формируется новый массив:
четные элементы (считая с нуля) - в первой половине, нечетные - во второй в обратном порядке, т.е. второй твой способ.

> сделать это за время O(N)

Igorek © (26.12.04 15:13) [58]
я имел ввиду память
но из "Так вот задача состоит в том, чтобы использовать только несколько дополнительных переменных, и минимизировать число операций (перестановок)."
ясо что затраты памяти O(1), а не например O(LogN)

default © (26.12.04 0:45) [36]
кстати довольно характерная черта людей - когда они что-то неплохо знают считать это за сомо собой разумеешееся и требовать того же от других
всё же лучше исходить из объективности
Вообще-то он прав, просто выразился вначале неверно. А вот это верно: Уметь писать программы - это часть компьютерной грамотности.

MBo © (26.12.04 7:07) [54]
Так вот задача состоит в том, чтобы использовать только несколько дополнительных переменных, и минимизировать число операций (перестановок).
В принципе, можно создавать очень большой массив, которого будет заведомо достаточно - условию это не противоречит.

Igorek © (26.12.04 9:49) [55]
- хорошенько поискать ответ на вопрос прежде чем постить на форумы
А я с этим не согласен. ИМХО, достаточно искать в F1 и MSDN, а уж Google и т.п. - это после форумов. Если уж искать, то искать на форумах. А если вопрос не стандартный, то и пытаться искать не стоит.

default © (26.12.04 16:26) [59]
я имел ввиду память
но из "Так вот задача состоит в том, чтобы использовать только несколько дополнительных переменных, и минимизировать число операций (перестановок)."
ясо что затраты памяти O(1), а не например O(LogN)
Видимо, решения с O(logN) и т.п. просто не получится выдумать.

Курс молодого бойца (читать - программиста) Найти похожие ветки