Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Вопрос только для Мастеров/прикладных программистов. [D1, D2, D3, D4, D5, D6, D7, Win95/98]

Страницы: 1 2 >
Evgeniy K © (2003-01-19 14:50:00)
Вопросик не для глупых.

Предпложим у меня есть матрица n*n, где n<251
Матрица заполнена числами.
1 3 4 10 15 ..
2 5 9 14 ..
4 8 13 ..
7 12 ..
11 ..

и т.д.
Мне дано какое-то число k. Как мне найти "координаты" этого числа в таблице?
Желательно чтобы на проверку 250^2 (250*250) чисел (k) уходило не более 1 сек.
Заранее все спасибо, кто хоть чем-то поможет.

PS Перебирать все числа нет смысла - времени не хватит, а как проще пока не догадался, поэтому и прошу вашей помощи, Мастера.
PSS Может формулу кто-нибудь знает?

MBo (2003-01-21 10:33:00) [1]
>Evgeniy_k
До чего же ты ленив ;(

procedure TForm1.Button1Click(Sender: TObject); var n, k, kk, x, y, d, diff: integer; procedure Calc; begin d := Ceil((Sqrt(1 + 8 * k) - 1) / 2); diff := (d * (d + 1) div 2) - k; y := diff + 1; x := d - diff; end; begin n := updown2.position; kk := updown1.position; if (kk <= 0) or (kk > n * n) then begin label1.caption := format("%d: Не входит в таблицу!", [kk]); Exit; end; k := kk; if k <= n * (n + 1) div 2 then Calc else begin k := n * n + 1 - k; Calc; x := n + 1 - x; y := n + 1 - y; end; label1.caption := format("%d: %d строка %d столбец", [kk, y, x]); end;

Robin Bobin (2003-01-21 09:55:00) [2]
Сдедай проще, знаешь как старая добрая игра "УГАДАЙ ЧИСЛО" ,делишь на 2, если больше, то делишь правую, если меньше, левую, итого, колличество проверок уменьшается в геометрической прогресиии. Дерзай мастер, можеш учебник по теории вероятности почитать...

Думкин (2003-01-21 06:46:00) [3]
Если матрица фиксирована и имеет всего 250 значений - зачем по ней лазить 65000 раз? В самом начале заполняем массив из 250 элементов соответствующими координатами - потом 65000 раз считываем значения этого массива - это уж точно в 1 сек уложится, если конечно у вас не арифмометр.

Про Кнута - он на примере этой задачи дает пример неверного индукционного предположения.

> и еще миллион задач из учебника, нет спасибо
А другого пути просто нет.

gsu (2003-01-21 02:15:00) [4]
>> Sha ©
Из уважения к вам, да и только, хоть вы и без медали (-:|~

Sha (2003-01-21 00:35:00) [5]
> Думкин © (20.01.03 14:17)
> Эффективность только может сильно варьировать.

О том и речь. У меня получилось штук 5 вариантов с разной эффективностью.

> gsu © (20.01.03 00:27)
> Раз поучительно, то я готов ее обозреть, если те не трудно
> gsu © (20.01.03 15:05)
> ..и еще миллион задач из учебника, нет спасибо

Зачем обозревал-то? :)))

gsu (2003-01-20 15:05:00) [6]
>> Sha ©
>> Ничто не мешает тебе ее решить
и еще миллион задач из учебника, нет спасибо

>> Так говорят твои учителя?
хм, каждому свое, ...

Думкин (2003-01-20 14:17:00) [7]

> > Думкин © (20.01.03 11:45)
> > Эта задача еще у Кнута упоминается, в самом первом томе
> в самом начале.
> Кнута читал давно, задачу эту не решал, наверное, посчитал
> очевидной. А когда недавно решил и рекурсией и циклом, получил
> глубокое удовлетворение. :)

У Кнута она не в плане нахождения решения приводится - запрограммировать ее - два пальца об асфальт. Эффективность только может сильно варьировать.
Там про что-то другое он писал - там в этой связи и Рамануджан упоминается.

Sha (2003-01-20 13:58:00) [8]
> gsu © (20.01.03 11:16)
> умёрла ? жаль.
Ничто не мешает тебе ее решить.

> gsu © (20.01.03 11:16)
> Кстати у рекурсии и циклов разные области применения ...
Так говорят твои учителя?

> Думкин © (20.01.03 11:45)
> Эта задача еще у Кнута упоминается, в самом первом томе в самом начале.
Кнута читал давно, задачу эту не решал, наверное, посчитал очевидной. А когда недавно решил и рекурсией и циклом, получил глубокое удовлетворение. :)

Evgeniy_k (2003-01-20 13:51:00) [9]
Я маленько описался, когда писал матрицу. Вот вам пример матрици, где n=5:
1 3 6 10 15
2 5 9 14 19
4 8 13 18 22
7 12 17 21 24
11 16 20 23 25

Тепер надеюсь понятно как заполняется матрица. Мне бы хотелось узнать существует ли формула для вычисления координат указанного элемента.
Спасибо всем, кто отвечал, но к сожалению еще не успел прочесть ваши постинги :( Завтра/послезавтра отвечу.

> Желательно чтобы на проверку 250^2 (250*250) чисел (k) уходило не более 1 сек.
Это значит, что координаты числа k будет искаться в матрице 62500 раз (на это должно уйти не более 1 сек).

> Начал неправильно. Сам-то к каким относишься?
> Если не глуп, то легко найдешь ответ.
Уже вроде нашел, но пока только в теории.

Evgeniy_k (2003-01-20 13:34:00) [10]
Большое спасибо. Посмотрю, попробую. Потом сообщу что получилось ;)

gsu (2003-01-20 12:05:00) [11]
>> Думкин ©
Может Сатир"у в институте такое задание дали(-:|~

Думкин (2003-01-20 11:45:00) [12]

> Sha © (20.01.03 11:09)
> Называлась Задача для разминки мозгов

> gsu © (20.01.03 11:16)
> >> Сатир © (25.12.02 14:49)
> но это ж комбинаторика.

Эта задача еще у Кнута упоминается, в самом первом томе в самом начале.

gsu (2003-01-20 11:16:00) [13]
>> но вроде умерла.
умёрла ? жаль.

>> Сатир © (25.12.02 14:49)
но это ж комбинаторика.

Кстати у рекурсии и циклов разные области применения и выражать их через друг друга можно, но не логично, так как цикл - это скорее алгоритмическая операция, а рекурсия - функциональная зависимость получения следующего элемента из предыдущего.
Верно ?

Sha (2003-01-20 11:09:00) [14]
> gsu © (20.01.03 00:27)
> Раз поучительно, то я готов ее обозреть, если те не трудно

ветка была такая http: //delphi.mastak.ru/cgi-bin/forum.pl?look=1&id=1040816965&n=3
но вроде умерла.

Называлась Задача для разминки мозгов

> Сатир © (25.12.02 14:49)
> есть ряд натуральных чисел от 1 до N
> есть число K
> Определить число комбинаций членов ряда, которые в сумме дадут K.
> Рассмотреть все варианты.

MBo (2003-01-20 10:32:00) [15]
>NailS
Да можно сразу решить уравнение n(n+1)/2<=k
;)

NailS (2003-01-20 10:06:00) [16]

> Reindeer Moss Eater (19.01.03 16:25)
> Матрица заполнена по тому же принципу, что в исходном сообщении
> или произвольно?
> Да никакой разницы нет, как она на самом деле заполнена.

Честно?
А мне казалось, что если известен алгоритм заполнения матрицы то искомый элемент можно просто вычислить.

> MBo © (19.01.03 17:17)
> j:=1;
> while a[1,j]<k do
> inc(j);
> i:=j-(a[1,j]-k);

А если использовать метод деления попалам, то еще быстрее будет ;))

atmamont (2003-01-20 01:06:00) [17]
а что, матрица вообще никаким законам распределения не поддается?

gsu (2003-01-20 00:27:00) [18]
Раз поучительно, то я готов ее обозреть, если те не трудно

Sha (2003-01-19 23:54:00) [19]
2 gsu © (19.01.03 23:08)

Вот и я - конечно нет. Главная проблема при использовании рекурсии состоит не в том, чтобы найти формулу, и даже не в том чтобы ее запрограммировать, а том что с первого взгляда не угадаешь, сколько лет все это будет работать. Вот тут Сатир недавно одну неплохую задачу давал на этот счет. Очень поучительно.

gsu (2003-01-19 23:08:00) [20]
>> даже по нескольким переменным идет без напряга?
Если б слушал все, чему учили (-:|~
Конечно нет. Я и не говорил, что это легко и я мастер рекурсии, так ..., ничего особого

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »