· Начало · Отвђтить · Статистика · Поиск · FAQ · Правила · Установки · Язык · Выход · WASM.RU · Noir.Ru ·

 WASM Phorum —› WASM.ZEN —› Дагонали треугольника Паскаля.

. 1 . 2 . >>

Посл.отвђт Сообщенiе


Дата: Июл 4, 2004 07:37:11 · Поправил: The Svin

Понадобилося сабж т.е.
выстроить сабж в линейку 1, 1,1, 1,2,1 , 1,3,3,1 и т.д.
Вот накидал рыбу.
Кажется задачка интересная, так что можно пообсуждать, есть кажется много возможностей улучшения

	xchg eax,edi
	movri eax,1
	movri ecx,3
	rep stosd
; edi=B
	mov ebx,2
@outer:
	xor ecx,ecx
	inc ecx
	mov dword ptr [edi],1
	mov eax,ebx
	shl eax,2
	neg eax		;eax=-G*4
	lea esi,[edi][eax][-4] ;esi=R
	
	@inner:
		mov eax,[esi][ecx*4] ;eax = R[i]
		add eax,[esi][ecx*4][4] ;eax =R[i]+R[i+1]
		mov [edi][ecx*4],eax ;B[i]=R[i]+R[i+1]
	    inc ecx
		cmp ecx,ebx
	jne @inner
	mov dword ptr [edi][ecx*4],1
	lea edi,[edi][ecx*4][4]
	inc ebx
	cmp ebx,33 ;на 33и диагонали можно больше если хочется.
jne @outer

Бляха муха. Ну как исправлять заголовки то?!


Дата: Июл 4, 2004 11:38:49

Маленькое улучшение:
	shl eax,2
	neg eax		;eax=-G*4
	lea esi,[edi][eax][-4] ;esi=R

Заменил на эквивалентный
	not eax
	lea esi,[edi][eax*4]


Дата: Июл 4, 2004 12:18:29

Оформил процедурой и несколько незначительных улучшений.
PascalD proc lpMemory,dCount
	pusha
	movri ecx,3
	mov edi,lpMemory
	cmp edx,ecx	;count < 3?
	sbb eax,eax
	jc @r
	movri eax,1
	rep stosd
; edi=B
	lea ebx,[ecx][2]	;ebx = 2
	lea edx,[ecx][-2]	;edx = -2
@outer1:
	xor ecx,ecx
	inc ecx
	dec edx				;edx=-ebx-1
	mov dword ptr [edi],ecx
	lea esi,[edi][edx*4] ;esi=R
	
	@inner2:
		mov eax,[esi][ecx*4] ;eax = R[i]
		add eax,[esi][ecx*4][4] ;eax =R[i]+R[i+1]
		mov [edi][ecx*4],eax ;B[i]=R[i]+R[i+1]
	    inc ecx
		cmp ecx,ebx
	jne @inner2
	mov dword ptr [edi][ecx*4],1
	lea edi,[edi][ecx*4][4]
	inc ebx
	cmp ebx,dCount 
jne @outer1
@r:	
	popa
	ret

PascalD endp


Дата: Июл 4, 2004 13:26:40

Тестирующая программа.
Исходник включён.

1432294329__PASCAL~1.RAR


Дата: Июл 6, 2004 02:36:35

The Svin
Тупизна моя не имент границ. Я для расширения кругозора пытаюсь просветиться (типа новый русский быдла и все такое), треугольник Паскаля - это, то что я пониаю??
121
12421
1248421

Блин, я конечно не прав, но что пониаеться под диагоналями треугольника Паскаля. Я могу понять диагонали там паралелограма, трапеции и т.д. но диагонали треугольника мое школьное образование мне не объяснило, я кое-как могу понять медины, бессектрисы и высоты, но до диагоналей еще не допер.

з.ы. прошу прощения, за орфографию, слегка не в себе, будет интересно если объясните............


Дата: Июл 6, 2004 03:42:43

Треугольник Паскаля:
11111
1234
136
14
1
И т.д.
Жирным шрифтом я отобразил одну из диагоналей. В данном случае 4ую (считая с нулевой)
Диагонали одно из самых интересных в треугольнике.
Пример из бинарных вещей, допустим тебе хочется узнать сколько может быть n битных (разрядных) чисел в которых только х бит установлены в 1.
Вот допустим интересно это про четырёх битные числа.
Смотришь на 4ю выделенную диагоноль.
4х битных чисел в которых 0 единичных бит (ни одного единичного бита) - одно,1 единичный бит - 4е, 2а единичных бита - 6, 3 единичных бита - 4е, 4е единичных бита (все биты единичные) - одно.
Это же ты можешь узнать про любое n разрядное число.
Посмотри на энную диагональ.
Пример из алгебры, допустим ты хочешь разложить на множетели (X+Y)n (т.е. биноминальное распределение)
Опять тут тебе поможет n ая диагональ, допустим опять о четырёх (X+Y)4
Четвёртая диагональ у тебя 1,4,6,4,1
(X+Y)4=
=1*X4+4X3Y+6X2Y2+4Y3X+1*Y4
Коэффициент 1 в 1*X4 я специально оставил чтобы показать соответсвие с диагональю его в обычной записью опускают и пишут просто X4
При вычислении искомого колличества n битных с x единичных бит тебе понадобалось бы очень тяжеловесная формула и трудно реализуемая как n!/(n-x)!(x)!
Достаточно сказать что максимальный факториал вместимый в 32х битное число это факториал 12и. Представь что нужно делать для нахождения факториала 32х например, если формулу кодировать в прямом виде.
Здесь же ты просто находишь n ую диагональ как сумму арифметической прогрессии до n (это всего лишь одно умножение и сдвиг)(это только если треугольник дан в таком компактном виде, можно расположить его в избыточность, тогда диагональ вообще быстрее находить) и смотришь x_ный элемент (вообще просто адресация по смещению, т.е. операция на адрес не требуется).
Сама же процедура показывает найденное рекурентное решение когда диагонали заполняются обычными сложение двух найденных предыдущих (отношение не линейное! каким бы простым код не казался! просто найдено удачное решение по рассчёту адресов нужных элементов).


Дата: Июл 6, 2004 04:14:14

sbb eax,eax
jc @r
movri eax,1

Как за это меня BlackMirror не поймал с его любовью к отлеживанию CF и adc,sbb? :)
можно смело сокращать на 2а байта:
sbb eax,eax
jc @r
inc eax


Дата: Июл 6, 2004 04:55:53

Диагональ - действительно некорректное обозначение в контексте треугольника. Но можно посмотреть на это с другой стороны: числа, формирующие треугольник являются прямоугольной матрицей, где недостающие члены - нули. И тогда числа, выделенные жирным, являются одной из диагоналей матрицы.


Дата: Июл 6, 2004 06:02:31 · Поправил: The Svin

Согласен.
Но согласившись с критикой, прошу обратить внимание на факт что "треугольник Паскаля" тоже не треугольник в смысле геометрическом.


Дата: Июл 6, 2004 06:14:42

Кстати, не могу не отметить, что сам термин диагональ, был использован самим Паскалем.
Он делил (группировал) числа в своём треугольнике по
"столбцам, строкам и диагоналям".
В частности он писал в мерсеновской переписке,
"сумма чисел по диагонали представляет собой два в степени номера строки".


Дата: Июл 6, 2004 08:21:52

Другая импровизация на ту же тему, позволяет найти xный элемент n_ой диагонали но без заполнения треугольника
Намного медленней, хотя избегает всё же вычислений факториалов на каждой стадии. CF если ошибка (x > n)
xPosINnDiag proc x,n
;вставьте сохранение регистров если нужно
	mov ecx,n
	test ecx,ecx
	je @r1
	cmp eax,x	
	sbb eax,eax
	jc @r
	inc eax
	mov ebx,eax

@@:  	mul ecx
	 	dec ecx
	 	div ebx
	 	inc ebx
	 	dec x
	 jne @r		
@r:	
	 ret
@r1: inc eax
	 jmp @r
xPosINnDiag endp


Дата: Июл 6, 2004 08:23:36 · Поправил: Black_mirror

„Как за это меня BlackMirror не поймал с его любовью к отлеживанию CF и adc,sbb? :)
можно смело сокращать на 2а байта: “


Смело можно сокращать в два раза:
PascalD:;(lpMemory, dCount)
	pusha
	mov esi,[32+esp+4];lpMemory
	mov edi,esi
	jmp .l2
    .l0:
	lodsd
	xchg eax,edx
	add eax,edx
	stosd
	cmp esi,ebp
	jb .l0
    .l2:
	xor edx,edx
	xor eax,eax
	inc eax
	stosd
	mov ebp,edi
	dec dword [32+esp+8];dCount
	jnz .l0
	popa
	ret


Дата: Июл 6, 2004 08:39:33

Работает. Здорово. Изучаю.


Дата: Июл 6, 2004 08:53:37

xchg eax,edx
add eax,edx

Заменим на> xadd eax,edx?
Размер тот же но быстрее по тестам.


Дата: Июл 6, 2004 09:36:28

The Svin
Поищи серию книг по полям Борисова(хотя за пределами Украины это будет проблематично). Они определяют бесконечные упорядоченные числовые ряды; доказывают многие биноминальные формулы, которые раньше давались как тождество; дают более общие формулы, из которых выводятся многие известные тождества.

В первой книжке рассмотрена обобщенная формула биноминальных коэффициентов на примере теугольника Паскаля.

. 1 . 2 . >>


Powered by miniBB 1.6 © 2001-2002
Время загрузки страницы (сек.): 0.056