Вопрос только для Мастеров/прикладных программистов.

← →
Evgeniy K (2003-01-19 14:50) [0]

Вопросик не для глупых.

Предпложим у меня есть матрица 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 Может формулу кто-нибудь знает?

← →
Reindeer Moss Eater (2003-01-19 14:53) [1]

С помощью чего реализована матрица?

← →
Романов Р.В. © (2003-01-19 15:13) [2]

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

← →
NailS © (2003-01-19 16:19) [3]

Матрица заполнена по тому же принципу, что в исходном сообщении или произвольно?

← →
Reindeer Moss Eater (2003-01-19 16:25) [4]

Матрица заполнена по тому же принципу, что в исходном сообщении или произвольно?
Да никакой разницы нет, как она на самом деле заполнена.
Важнее то, как её элементы расположены в памяти. Непрерывным блоком или нет. Если непрерывным, то перебора элементов по индексам можно избежать.

← →
Sha © (2003-01-19 17:05) [5]

> Evgeniy K (19.01.03 14:50)
> Вопросик не для глупых.

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

← →
Mystic © (2003-01-19 17:08) [6]

Наверняка не самое оптимальное, но работает быстрее 1 мин ;)

I := 2; Step := 2; while I <= N do begin I := I + Step; Step := Step + 1; end; X := N + Step - I; Y := Step - X;

← →
MBo © (2003-01-19 17:17) [7]

j:=1;
while a[1,j]<k do
inc(j);
i:=j-(a[1,j]-k);

i,j - строка, столбец.

← →
gsu © (2003-01-19 18:00) [8]

Забежал на сек, интересно !
Вот, те прикладная рекурсия (-:|~
x ={0,n} - столбцы
y={0,n} - строки
diag(0)=1
diag(m)=diag(m-1)+m, m={1..n-1}
pair(x,y)=diag(x+y)+y
Вот и все, например: pair(1,2)=diag(3)+2=9

← →
gsu © (2003-01-19 18:01) [9]

И причем здесь глупость ?
Глупых не бывает, бывают ленивые и/или упертые

← →
Sha © (2003-01-19 18:19) [10]

2 MBo © (19.01.03 17:17)
2 gsu © (19.01.03 18:00)

есть способ проще:
procedure TForm1.Button2Click(Sender: TObject); var k, n, m: integer; begin; k:=14; n:=0; m:=0; repeat; inc(n); inc(m,n); until m>=k; m:=m-k+1; n:=n-m+1; ShowMessage(Format("%d находится в строке %d колонке %d",[k,m,n])); end;

2 Evgeniy K (19.01.03 14:50)
А вообще-то нехорошо начинать ветку так Вопрос только для Мастеров.
Остальным типа не соваться в мою ветку. Хочу с Мастерами говорить.

← →
Sha © (2003-01-19 18:24) [11]

2 Mystic © (19.01.03 17:08)

Извини, у нас совпало :)

← →
gsu © (2003-01-19 18:40) [12]

Что может быть проще рукурсии ? (-:|~
Говорят, что все создано из пяти основных эл-тов и рекурсии, н-р, у человека 5 пальцев, 5 ...
Но я в этом не уверен, так как не создатель (-:|~

← →
gsu © (2003-01-19 18:42) [13]

>> Хочу с Мастерами говорить.
типа, у мя проездной (-:|~

← →
Sha © (2003-01-19 18:52) [14]

> gsu © (19.01.03 18:40)
> Что может быть проще рукурсии ? (-:|~

Не лукавишь? Для меня цикл намного проще. Когда в задаче встречается рекурсия приходится как-то непроизвольно собираться. Затянувшееся последействие института. :(

← →
gsu © (2003-01-19 19:29) [15]

>> приходится как-то непроизвольно собираться
Может, и у мя раньше такое было, но благодаря супер учителям (подготовка) и опосля, реализациям всяких мат. методов меня рекурсия начала радовать. Только думать надо и не везде применимо, зато какие изящные решения.

← →
Sha © (2003-01-19 22:14) [16]

> gsu © (19.01.03 19:29)
> но благодаря супер учителям (подготовка) и опосля, реализациям
> всяких мат. методов меня рекурсия начала радовать

даже по нескольким переменным идет без напряга?

← →
gsu © (2003-01-19 23:08) [17]

>> даже по нескольким переменным идет без напряга?
Если б слушал все, чему учили (-:|~
Конечно нет. Я и не говорил, что это легко и я мастер рекурсии, так ..., ничего особого

← →
Sha © (2003-01-19 23:54) [18]

2 gsu © (19.01.03 23:08)

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

← →
gsu © (2003-01-20 00:27) [19]

Раз поучительно, то я готов ее обозреть, если те не трудно

← →
atmamont © (2003-01-20 01:06) [20]

а что, матрица вообще никаким законам распределения не поддается?

← →
NailS © (2003-01-20 10:06) [21]

> 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);

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

← →
MBo © (2003-01-20 10:32) [22]

>NailS
Да можно сразу решить уравнение n(n+1)/2<=k
;)

← →
Sha © (2003-01-20 11:09) [23]

> 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.
> Рассмотреть все варианты.

← →
gsu © (2003-01-20 11:16) [24]

>> но вроде умерла.
умёрла ? жаль.

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

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

← →
Думкин © (2003-01-20 11:45) [25]

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

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

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

← →
Evgeniy_k (2003-01-20 13:34) [27]

Большое спасибо. Посмотрю, попробую. Потом сообщу что получилось ;)

← →
Evgeniy_k (2003-01-20 13:51) [28]

Я маленько описался, когда писал матрицу. Вот вам пример матрици, где 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 сек).

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

> gsu © (20.01.03 11:16)
> умёрла ? жаль.
Ничто не мешает тебе ее решить.

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

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

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

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

>> Sha ©
>> Ничто не мешает тебе ее решить
и еще миллион задач из учебника, нет спасибо

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

> Думкин © (20.01.03 14:17)
> Эффективность только может сильно варьировать.

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

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

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

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

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

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

← →
Robin Bobin (2003-01-21 09:55) [35]

Сдедай проще, знаешь как старая добрая игра "УГАДАЙ ЧИСЛО" ,делишь на 2, если больше, то делишь правую, если меньше, левую, итого, колличество проверок уменьшается в геометрической прогресиии. Дерзай мастер, можеш учебник по теории вероятности почитать...

>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;

Вопрос только для Мастеров/прикладных программистов. Найти похожие ветки