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

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

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

помогите накодить штуку( [D7]

Страницы: 1 2 3 >
Григорий © (2011-06-01 21:36:00)
Составить программную реализацию следующей игры: вдоль доски расположены лунки и в каждой .лунке лежит шар черного или белого цвета. Одним ходом разрешается менять местами два любых шара. Добиться того, чтобы сначала шли белые шары, а за ними - черные. Количество лунок вводится с клавиатуры, расположение шаров задается с помощью датчика случайных чисел.

Dennis I. Komarov (2011-06-03 09:46:00) [1]

> Юрий Зотов © (02.06.11 18:17) [41]

Не совсем то :)

> на выходе получить последовательность чисел, каждое из которых
> указывает операцию перемещения, соответствующие биты которого
> "1" остальные "0"

З.Ы.
Д.Юра, я ни капли не сомневаюсь, что Вы полностью постигли дао логических операций, пусть те кто еще не познал всей сути бытия единиц и нулей напрягают извилины ;)

Inovet (2011-06-02 19:11:00) [2]
> [41] Юрий Зотов © (02.06.11 18:17)
> FFFFFFFF shr (
> Z[i and FF] + Z[(i shr 4) and FF] + Z[(i shr 8) and FF] + Z[(i shr 12) and FF]
> + Z[(i shr 16) and FF] + Z[(i shr 20) and FF] + Z[(i shr 24) and FF] + Z[(i shr 28)])

как-то так ещё быстрее

на входе в eax число
на выходе число в edx

mov ecx, 32
xor edx, edx
lbc:
rcl eax
jnc lbo
rcl edx
lb0:
loop lbc

Юрий Зотов (2011-06-02 18:19:00) [3]
Блин... FF везде заменить на F

Юрий Зотов (2011-06-02 18:17:00) [4]
Массив Z[0..FF]:

00 - 2
01 - 1
10 - 1
11 - 0
100 - 2
101 - 1
110 - 1
111 - 0
1000 - 3
1001 - 2
1010 - 2
1011 - 1
1100 - 2
1101 - 1
1110 - 1
1111 - 0

Ответ:

FFFFFFFF shr (
Z[i and FF] + Z[(i shr 4) and FF] + Z[(i shr 8) and FF] + Z[(i shr 12) and FF]
+ Z[(i shr 16) and FF] + Z[(i shr 20) and FF] + Z[(i shr 24) and FF] + Z[(i shr 28)])

Dennis I. Komarov (2011-06-02 18:05:00) [5]

> Юрий Зотов © (02.06.11 17:43) [39]

да это понятно, но из [0]:

> Одним ходом разрешается менять местами два любых шара.

да и [38] дописал...

Юрий Зотов (2011-06-02 17:43:00) [6]
> Dennis I. Komarov © (02.06.11 16:43) [36]

1. Сосчитать N - количество нулевых бит в 32-битном целом (проще и быстрее всего сделать это по заранее составленной таблице).
2. Ответ: $FFFFFFFF shr N

Dennis I. Komarov (2011-06-02 17:08:00) [7]

> А если результат - то получается что нужно на выходе получить
> число,

Не совсем. Данная задача направлена на изучение логических операций, т.е. смысл составить алгоритм и закодировать его. Ценность в самой программе, т.е. уменее ее написать нежели результат.

Для полноты задания: на выходе получить последовательность чисел, каждое из которых указывает операцию перемещения, соответствующие биты которого "1" остальные "0"

Очень злой (2011-06-02 17:02:00) [8]

> 1. выполнить [0] с помощью логических операций (or and xor
> shl и т.п)

Все зависит от того что тут важно: процесс или сам результат...
В [0] был важен процесс, т.е. обмен местами двух шаров...
А если результат - то получается что нужно на выходе получить число, у которого столько же единиц, сколько и у исходного значения, только все единицы сдвинуты к одному (навенрое правому) краю.

> З.Ы. Задача (хотя и не пятница) для новечков

Эх. Когдато МВо каждую пятницу задачки выкладывал... Интерестно было...
А сейчас что-то уже давно нет задачек... :(

Dennis I. Komarov (2011-06-02 16:43:00) [9]
Давайте усложним:
Допустим кол-во шаров <=32

на вход подается случайное целое (32 bit) - есть первоначальное положение шаров: 0 - белый, 1 - другой
1. выполнить [0] с помощью логических операций (or and xor shl и т.п)
2. выполнить данную сортировку за минимальное кол-во перемещений

З.Ы. Задача (хотя и не пятница) для новечков

Очень злой (2011-06-02 15:45:00) [10]

> PS
> Странно, но когда новичку требовалась помощь, Вас в ветке
> почему-то не было. А когда она уже не требовалась, Вы появились.
>

Просто я на форум зашел поздно.

Да и извиняюсь конечно, но просто не обратил внимания не этот пост:

> Григорий (01.06.11 21:52) [2]
>
> да

Inovet (2011-06-02 15:35:00) [11]
> [32] KilkennyCat © (02.06.11 15:29)
> любят задачки про шары....

Карманный биллиард даёт о себе знать.

Inovet (2011-06-02 15:33:00) [12]
> [0] Григорий (01.06.11 21:36)
> Одним ходом разрешается менять местами два любыхшара.

> [1] Юрий Зотов © (01.06.11 21:40)
> Пузырьковая сортировка?

> [2] Григорий (01.06.11 21:52)
> да

По условию получается необязательно пузырьковая.

KilkennyCat (2011-06-02 15:29:00) [13]
любят задачки про шары....

Юрий Зотов (2011-06-02 15:17:00) [14]
> Очень злой
Вот нормальный пузырек:
for i := 1 to Len - 1 do for j := 1 to Len - i do if Arr[j] > Arr[j + 1] then begin A := Arr[j]; Arr[j] := Arr[j + 1]; Arr[j + 1] := A; end;
И оптимальнее этого Вы пузырек не напишете. А если хотите поговорить о КОНКРЕТНОЙ задаче, где только черное и белое, то давайте именно о НЕЙ и поговорим. И для начала прочитаем ее условие - требуется сделать ИГРУ. В которой никакая оптимизация и вовсе не нужна, потому что визуальные перестановки сожрут в миллион раз больше времени, чем сама сортировка.

PS
Странно, но когда новичку требовалась помощь, Вас в ветке почему-то не было. А когда она уже не требовалась, Вы появились.

Inovet (2011-06-02 14:59:00) [15]
> [27] Очень злой (02.06.11 14:34)
> 3. Сложность алгоритма - N

Так и с одного конца тоже получается ведь.

Очень злой (2011-06-02 14:57:00) [16]

> В условии задачи нет "за минимальное время/количество перестановок"
> :)))

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

oldman (2011-06-02 14:45:00) [17]

> Очень злой (02.06.11 14:34) [27]
> > Да, непонятен смысл прохода с двух концов.
> 1. так достигается минимальное количество обменов шариков.

В условии задачи нет "за минимальное время/количество перестановок"
:)))

Очень злой (2011-06-02 14:34:00) [18]

> Да, непонятен смысл прохода с двух концов.

1. так достигается минимальное количество обменов шариков.
2. если не учитывать сам процесс обмена, то каждый элемент массива шариков проверяется только один раз.
3. Сложность алгоритма - N, а у этого:

> for i := Len downto 1 do
> for j := 1 to Len - 1 do
> if Arr[j] > Arr[j + 1] then
> begin
> A := Arr[j];
> Arr[j] := Arr[j + 1];
> Arr[j + 1] := A;
> VisualSwap(j, j + 1)
> end

N^2
Да и внутренние циклы - просто "прокручивают" переменные, облегчая работу внешненго цикла. Посему теоретически это все-таки один проход, несмотря на вложенные циклы...

oldman (2011-06-02 14:27:00) [19]

> Очень злой (02.06.11 13:15) [23]

А не проще (для, например, черного цвета):

I=1

Идем с позиции I, пока не встретим шар белого цвета. Запоминаем позицию N.
Идем дальше, пока не встретим шар черного цвета L на позиции М.
(Если не встретили - конец сортировки)
Меняем шар L с шаром M-1, пока L не достигнет N
I=N+1
Возвращаемся к началу прохода

Inovet (2011-06-02 14:05:00) [20]
Да, непонятен смысл прохода с двух концов.

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

Наверх

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