memold ([info]memold) wrote in [info]ru_programming,
@ 2008-05-09 00:18:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Господа, профессионалы, подскоажите пожалуйста :-)
Помогите с верою в правильность собственных решений.
Без реализации, а просто советы.
СПАСИБО.


Задание 1.
Решить двумя способами (простым способом и быстрым способом) следующую задачу: написать
функцию, которая возвращает количество нулевых бит в символах строки (не считая нулевой символ в
конце строки):
int CountZeroBits(const char *s)

Задание 2.
Дан массив произвольного размера с числами в пределах от 1 до 1,000,000. В этом массиве все числа
уникальные, кроме одного числа, которое повторяется два раза. Найти это число. Решить эту задачу с
минимально возможным использованием процессорного времени.

(Post a new comment)


[info]cathody
2008-05-08 08:40 pm UTC (link)
О! Пятничный пост!

(Reply to this)


[info]aklirud_lorap
2008-05-08 08:43 pm UTC (link)
Ну объясните мне, пожалуйста, нафига это?

(Reply to this)


[info]aru
2008-05-08 09:06 pm UTC (link)
я тут выпил... в последнем сложность Н?

(Reply to this)


[info]glebych
2008-05-08 10:12 pm UTC (link)
а я вот начал сомневаться: все время думал, что строка из байтов состоит. Может, ошибался? или речь рально о битах в кодах символов?

(Reply to this) (Thread)

[info]memold
2008-05-09 11:51 am UTC (link)
Речь шла об этом.

Вот функция подсчета единиц а байте.

Приблизительно это я искал.

BYTE ?::numofbit(BYTE x)
{
x = (x & 0x55) + ((x >> 1) & 0x55);
x = (x & 0x33) + ((x >> 2) & 0x33);
x = (x & 0x0F) + ((x >> 4) & 0x0F);

return x;
}

(Reply to this) (Parent)

[info]backa
2008-05-09 02:25 pm UTC (link)
Строки разные бывают. :)

(Reply to this) (Parent)

[info]cathody
2008-05-08 10:57 pm UTC (link)
Решить эту задачу с
минимально возможным использованием процессорного времени.

Нанять счетовода. Тогда процессорное время вообще не понадобится.

(Reply to this)


[info]de_maniac
2008-05-09 03:02 am UTC (link)
Ну с 1ым не понятно про простой и быстрый

быстрый наверное так... %)

mov AX, SEG arr
mov ES, AX
mov BX, offset arr
xor DX, DX

mov CX, len
@a:
mov AX, ES:[BX]
push CX
mov CX, 16
@b:
shr AX, 1
jc @k
inc DX
@k:
loop @b
pop CX
inc BX
loop @a

Если длинная не дана, то

@a:
mov AX, ES:[BX]
jz @end
mov CX, 16
@b:
shr AX, 1
jc @k
inc DX
@k:
loop @b
inc BX
jmp @a
@end:

(Reply to this) (Thread)

[info]de_maniac
2008-05-09 03:07 am UTC (link) 
mov AX, SEG arr
mov ES, AX
mov BX, offset arr
xor DX, DX

mov CX, len
@a:
  mov AX, ES:[BX]
  push CX
  mov CX, 16
  @b:
    shr AX, 1
    jc @k
      inc DX
    @k:
  loop @b
  pop CX
  inc BX
loop @a

Если длинная не дана, то

@a:
  mov AX, ES:[BX]
  jz @end
  mov CX, 16
  @b:
    shr AX, 1
    jc @k
      inc DX
    @k:
  loop @b
  inc BX
jmp @a
@end:

(Reply to this) (Parent)

[info]cathody
2008-05-09 03:12 am UTC (link)
Это чистое два :)

(Reply to this) (Parent)

[info]memold
2008-05-09 11:54 am UTC (link)
Я так понял здес подсчитываются нулевые байты, а не биты.

(Reply to this) (Parent)

[info]madf
2008-05-09 05:25 am UTC (link)
1. Класика жанра.
Забиваем масив на 256 элементов. В каждом храним кол-во нулей в этом числе. Потом гуляем по строке от начала до конца и суммируем. Сложность O(n)
2. Условие не совсем правильное - массив ограничен длиной 1000001 элементов.
Минимум итераций - это подготовить массивчик на 1000000 элементов, инициализированный нулями. Гулаем по исходному и инкрементируем соответствующие элементы. Как только получим 2 - выходим. Сложность в худшем случае будет O(n)

(Reply to this) (Thread)

[info]earwin
2008-05-09 06:53 am UTC (link)
А теперь всё то-же самое и с такой-же скоростью, но с константной дополнительной памятью, или вообще без оной.

(Reply to this) (Parent)(Thread)

[info]madf
2008-05-09 07:05 am UTC (link)
Прямой подсчет битов тоже даст линейное время, т.к. длина байта константна.
По второму отпишу вечерои - сейчас уходить надо

(Reply to this) (Parent)(Thread)

[info]madf
2008-05-09 07:09 am UTC (link)
Хех. Проверка на дубликаты: идем по массиву, для каждого элемента считаем v = 2^x. Делаем проверку (sum & v) == v. Если равно - дубликат. В противном случае делаем sum |= v.
Сложность как и в первом варианте. Памяти чуть меньше.

(Reply to this) (Parent)

[info]avs313
2008-05-09 06:26 am UTC (link)
2 - отсортировать массив и все
1 - как уже говорили, делаем табличку и все
если не умеете нулики в битах считать, всегда можно руками забить :D

(Reply to this) (Thread)

[info]earwin
2008-05-09 06:51 am UTC (link)
Отсортировать, да-да. И всё, да-да. И ещё посканить результат, да-да.
Минимум итераций, ню-ню.

(Reply to this) (Parent)(Thread)

[info]avs313
2008-05-09 06:55 am UTC (link)
нет бля, нужно для массива в 100 элементов таблицу на весь миллион проинициализировать, да?

(Reply to this) (Parent)(Thread)

[info]aceler
2008-05-09 07:48 am UTC (link)
Надо в MySQL запихать.

(Reply to this) (Parent)

[info]earwin
2008-05-09 09:59 am UTC (link)
Нет, надо мозг проинициализировать. Задача решается за линейное время и без дополнительной памяти.

(Reply to this) (Parent)(Thread)

[info]madf
2008-05-09 03:56 pm UTC (link)
Алгоритм - в студию!

(Reply to this) (Parent)(Thread)

[info]earwin
2008-05-09 04:29 pm UTC (link)
xor :)

(Reply to this) (Parent)(Thread)

[info]madf
2008-05-09 05:09 pm UTC (link)
И чем он поможет?
Нет уж, xor'ом единым сыт не будешь! Тем более без математического обоснования...
1 ^ 2 ^ 1 = 2
1 ^ 2 ^ 2 = 1
1 ^ 2 ^ 3 ^ 1 = 1
1 ^ 2 ^ 3 ^ 2 = 2
И т.д. Тем более что числа-то - произвольные!

(Reply to this) (Parent)(Thread)

[info]earwin
2008-05-10 10:24 am UTC (link)
Я тупое животное. Надо было условие лучше читать.
Так что мозг действительно надо проинициализировать, но пожалуй что мне :)

(Reply to this) (Parent)(Thread)

[info]madf
2008-05-10 10:54 am UTC (link)
Бывает...
Но когда ты про xor написал - я надолго задумался. Нужели что-то очевидное упустил? :)

(Reply to this) (Parent)(Thread)

[info]earwin
2008-05-10 11:28 am UTC (link)
Есть просто целая серия похожих по формулировке задач, которые решаются если вспомнить про всякие коды коррекции ошибок, в тупом случае - при помощи xor (типа "все дубликаты кроме одного", или "одно число выпало").

(Reply to this) (Parent)

[info]migmit
2008-05-09 08:38 am UTC (link)
Передайте преподу моё "буэ" на неуникодные строки.

(Reply to this) (Thread)

[info]sb16
2008-05-09 09:58 am UTC (link)
Кто мешает забить в char * юникод? Алгоритм не изменится, мы перебираем биты до первого байта 0x00. В уникоде их будет N штук подряд, это единственная разница.

(Reply to this) (Parent)

[info]lonelycactus
2008-05-09 09:55 am UTC (link)
этот пост сожрал столько процессорного времени, что аж волосы на жопе дыбом встают.

а вопрос про нулевые биты так ещё и моск мой сжёг.

(Reply to this)


[info]backa
2008-05-09 02:29 pm UTC (link)
Если не изменяет память, обе эти и ещё многие другие задачи подробно рассмотрены в книге "Жемчужины программирования".

(Reply to this)

Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…