ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Другие СУБД [игнор отключен] [закрыт для гостей] / Лучшие задачи проекта
25 сообщений из 191, страница 5 из 8
  5  все
Лучшие задачи проекта
    #38099618
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
Да
...
Рейтинг: 0 / 0
03.01.2013, 21:02
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099636
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Акей. Прикину на глаз.

И сделаю общую постановку для любого массива.

Дано массив 32-х битных целых (Ai). Надо найти минимальный и макс бит (позиции).

1) Для массива из 1 числа выдаём пустое множество.

2) Для двух чисел A(0) и A(1) разница - это A(0) XOR A(1).

3) Для произвольного N чисел - заводим два доп регистра.
Amax=0xFFFFFFFF и Amin=0x00000000.

В цикле для всех A(N) сбрасываем биты Amax и устанавливаем биты Amin.

В конце сравниваем Amax и Amin. И выдаём расстояние Хемминга H(Amax,Amin).

Для H(..) вычисляем ненулевой левый и правый бит.

Готово.

Сложность - O(n).

P.S. Вообще Баз ты по сабжу наглец! Ты краудсорсингом собираешь из нас солюшены
а потом имплементируешь и выдаёшь за свои. Гарантирую что ты эти задачки
специально придумал. Не так ли?
...
Рейтинг: 0 / 0
03.01.2013, 21:16
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099641
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Поправка. Без Хэмминга. Просто посчитаем что H(Amin,Amax)=xor(Amin,Amax)
...
Рейтинг: 0 / 0
03.01.2013, 21:17
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099647
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
Давай на Си код, сколько операций будет для 4х чисел ?
Все ищут более менее не комбинаторное решение
...
Рейтинг: 0 / 0
03.01.2013, 21:27
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099695
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Почему для 4-х чисел? Я не согласен с такой постановкой.
Ты меня искусственно ограничил. Объясни зачем 4 числа?
...
Рейтинг: 0 / 0
03.01.2013, 23:16
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099702
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
И при чем здесь комбинаторное? Я-же написал O(n). Линейное.
...
Рейтинг: 0 / 0
03.01.2013, 23:26
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099740
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
maytonИ при чем здесь комбинаторное? Я-же написал O(n). Линейное.

По-поводу моей задачи, можно сделать оптимальней чем линейное, сделать рекурсивный спуск (но это прикидка). В любом случае - приведи хотябы псевдо код своего решения.
Кстате не нужно забывать что могут быть контр примеры. Например лучший блок может быть и таким.

0000 1101 0111 0010 010 1 0010 0101 1101
0000 1101 0111 0010 010 1 0110 0101 1101
0000 1101 0111 0010 011 1 0010 0101 1101
0000 1101 0111 0010 110 1 0010 0101 1101

По всем остальным блокам, совпадений больше двух. Поэтому нужно вернуть лучший из найденых блоков.


По-поводу твоей задачи, пришла в голову мысль на счет сжатия. Если все даты рождений отсортировать по возрастанию, то получится между соседними датами небольшая разница.
Ну допустим от 0 до 15 минут. Вот через дельту и можно кодировать каждое следующее число. Наилучшее сжатие тут может быть в 32 раза ...
...
Рейтинг: 0 / 0
04.01.2013, 00:34
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099744
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
maytonАкей. Прикину на глаз.

И сделаю общую постановку для любого массива.

Дано массив 32-х битных целых (Ai). Надо найти минимальный и макс бит (позиции).

1) Для массива из 1 числа выдаём пустое множество.

2) Для двух чисел A(0) и A(1) разница - это A(0) XOR A(1).

3) Для произвольного N чисел - заводим два доп регистра.
Amax=0xFFFFFFFF и Amin=0x00000000.

В цикле для всех A(N) сбрасываем биты Amax и устанавливаем биты Amin.

В конце сравниваем Amax и Amin. И выдаём расстояние Хемминга H(Amax,Amin).

Для H(..) вычисляем ненулевой левый и правый бит.

Готово.

Сложность - O(n).

P.S. Вообще Баз ты по сабжу наглец! Ты краудсорсингом собираешь из нас солюшены
а потом имплементируешь и выдаёшь за свои. Гарантирую что ты эти задачки
специально придумал. Не так ли?


Я думал о похожем решении вчера
но Баз расставил точки над Ё

авторМинимальный три, потому что для трех бит на этой позиции действует условие:
110 != 100 != 111 != 001
Еслиб условие не действовало, тогда бы пришлось захватить еще один бит ( как вариант ).


То есть должна соблюдаться уникальность .

Так , баз ?

В примере есть другой блок из 2 бит ,
но там уникальности нет, в 2 строках одинаковые последовательности бит.
...
Рейтинг: 0 / 0
04.01.2013, 00:41
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099746
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BAZlSTПо-поводу твоей задачи, пришла в голову мысль на счет сжатия. Если все даты рождений отсортировать по возрастанию, то получится между соседними датами небольшая разница.
Ну допустим от 0 до 15 минут. Вот через дельту и можно кодировать каждое следующее число. Наилучшее сжатие тут может быть в 32 раза ...
Там нету кодирования минут. Только целые дни. Первоисточник по формату ИНН здесь
http://zliypes.com.ua/blog/2007/10/29/ukrainian-pti/
...
Рейтинг: 0 / 0
04.01.2013, 00:43
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099749
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
ДохтаРавторМинимальный три, потому что для трех бит на этой позиции действует условие:
110 != 100 != 111 != 001
Еслиб условие не действовало, тогда бы пришлось захватить еще один бит ( как вариант ).


То есть должна соблюдаться уникальность .

Так , баз ?

В примере есть другой блок из 2 бит ,
но там уникальности нет, в 2 строках одинаковые последовательности бит.

Нужно вернуть лучший найденый блок минимальной длины.
В примере выше блок из трех бит, и все четыре числа по этому блоку не совпадают.
В контр примере нет четырех блоков отличающихся друг от друга, тогда нужно вернуть наилучшее решение, в данном случае где три блока отличаются между собой.
...
Рейтинг: 0 / 0
04.01.2013, 00:45
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099750
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
BAZlSTmaytonИ при чем здесь комбинаторное? Я-же написал O(n). Линейное.

По-поводу моей задачи, можно сделать оптимальней чем линейное, сделать рекурсивный спуск (но это прикидка). В любом случае - приведи хотябы псевдо код своего решения.
Кстате не нужно забывать что могут быть контр примеры. Например лучший блок может быть и таким.

0000 1101 0111 0010 010 1 0010 0101 1101
0000 1101 0111 0010 010 1 0110 0101 1101
0000 1101 0111 0010 011 1 0010 0101 1101
0000 1101 0111 0010 110 1 0010 0101 1101

По всем остальным блокам, совпадений больше двух. Поэтому нужно вернуть лучший из найденых блоков.


По-поводу твоей задачи, пришла в голову мысль на счет сжатия. Если все даты рождений отсортировать по возрастанию, то получится между соседними датами небольшая разница.
Ну допустим от 0 до 15 минут. Вот через дельту и можно кодировать каждое следующее число. Наилучшее сжатие тут может быть в 32 раза ...

Баз ты вобще сам то знаешь что те нужно

Чем это решение из вчерашнего примера непоходит ?
00 00 1101 0111 0010 0101 0010 0101 1101
00 11 1101 0111 0010 0101 0101 0101 1001
00 00 1101 0100 0010 0101 0010 0101 1111
00 10 1101 0101 0010 0101 0010 0101 0010
...
Рейтинг: 0 / 0
04.01.2013, 00:47
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099751
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
maytonBAZlSTПо-поводу твоей задачи, пришла в голову мысль на счет сжатия. Если все даты рождений отсортировать по возрастанию, то получится между соседними датами небольшая разница.
Ну допустим от 0 до 15 минут. Вот через дельту и можно кодировать каждое следующее число. Наилучшее сжатие тут может быть в 32 раза ...
Там нету кодирования минут. Только целые дни. Первоисточник по формату ИНН здесь
http://zliypes.com.ua/blog/2007/10/29/ukrainian-pti/

тогда точно сжатие может составить 32 раза.
Каждый день ктото рождался и дату рождения каждого следующего ребенка кодируй 0, если его дата не отличается от преведущей даты рождения, и 1 если отличается на один день.
...
Рейтинг: 0 / 0
04.01.2013, 00:47
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099755
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
ДохтаРBAZlSTпропущено...


По-поводу моей задачи, можно сделать оптимальней чем линейное, сделать рекурсивный спуск (но это прикидка). В любом случае - приведи хотябы псевдо код своего решения.
Кстате не нужно забывать что могут быть контр примеры. Например лучший блок может быть и таким.

0000 1101 0111 0010 010 1 0010 0101 1101
0000 1101 0111 0010 010 1 0110 0101 1101
0000 1101 0111 0010 011 1 0010 0101 1101
0000 1101 0111 0010 110 1 0010 0101 1101

По всем остальным блокам, совпадений больше двух. Поэтому нужно вернуть лучший из найденых блоков.


По-поводу твоей задачи, пришла в голову мысль на счет сжатия. Если все даты рождений отсортировать по возрастанию, то получится между соседними датами небольшая разница.
Ну допустим от 0 до 15 минут. Вот через дельту и можно кодировать каждое следующее число. Наилучшее сжатие тут может быть в 32 раза ...

Баз ты вобще сам то знаешь что те нужно

Чем это решение из вчерашнего примера непоходит ?
00 00 1101 0111 0010 0101 0010 0101 1101
00 11 1101 0111 0010 0101 0101 0101 1001
00 00 1101 0100 0010 0101 0010 0101 1111
00 10 1101 0101 0010 0101 0010 0101 0010

тем что здесь совпадают два числа.
А алгоритм такой - самое лучшее решение, где все четыре блока минимальной длины не совпадают между собой.
Если такого не найдено, вернуть решение где хотябы три блока не совпадают.
Если такого не найдено, хотябы два блока не совпадают.
Если не найдено, то феил.
...
Рейтинг: 0 / 0
04.01.2013, 00:49
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099756
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BAZlSTПо-поводу моей задачи, можно сделать оптимальней чем линейное, сделать рекурсивный спуск (но это прикидка). В любом случае - приведи хотябы псевдо код своего решения.
Кстате не нужно забывать что могут быть контр примеры. Например лучший блок может быть и таким.
Псевдокод. Общий случай. A(i) - произвольные. Нет монтонной последовательности.
Нет кода Грея. Нет энтропиии. Абсолютные шумящие случайные.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
...
i=0;
Amin=0x0000 0000;
Amax=0xFFFF FFFF;
while(i<N){
   Amin = Amin OR A(i);
   Amax = Amax AND A(i);
}
print("Distance = ",distance(Amin XOR Amax));
...
Рейтинг: 0 / 0
04.01.2013, 00:50
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099758
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Инкремент в цикл вставить забыл.
Код: plaintext
1.
i++;
...
Рейтинг: 0 / 0
04.01.2013, 00:51
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099761
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
maytonBAZlSTПо-поводу моей задачи, можно сделать оптимальней чем линейное, сделать рекурсивный спуск (но это прикидка). В любом случае - приведи хотябы псевдо код своего решения.
Кстате не нужно забывать что могут быть контр примеры. Например лучший блок может быть и таким.
Псевдокод. Общий случай. A(i) - произвольные. Нет монтонной последовательности.
Нет кода Грея. Нет энтропиии. Абсолютные шумящие случайные.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
...
i=0;
Amin=0x0000 0000;
Amax=0xFFFF FFFF;
while(i<N){
   Amin = Amin OR A(i);
   Amax = Amax AND A(i);
}
print("Distance = ",distance(Amin XOR Amax));



1. Где приращение "i" ?
2. Программа должна выводить два числа. Смещение слева и размер блока бит.
...
Рейтинг: 0 / 0
04.01.2013, 00:52
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099764
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
BAZlST
0000 1101 0111 0010 010 1 0010 0101 1101
0000 1101 0111 0010 010 1 0110 0101 1101
0000 1101 0111 0010 011 1 0010 0101 1101
0000 1101 0111 0010 110 1 0010 0101 1101

ДохтаРпропущено...


Баз ты вобще сам то знаешь что те нужно

Чем это решение из вчерашнего примера непоходит ?
00 00 1101 0111 0010 0101 0010 0101 1101
00 11 1101 0111 0010 0101 0101 0101 1001
00 00 1101 0100 0010 0101 0010 0101 1111
00 10 1101 0101 0010 0101 0010 0101 0010

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

Так какое лучше ?
2 битный блоки с 3 уникальными знасениями, или 2 битные с 3 уникальными значениями ?

Баз , а вчера где ты был , почему про условия лучшести блоков не рассказал ?
...
Рейтинг: 0 / 0
04.01.2013, 00:57
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099765
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
BAZlSTДохтаРпропущено...


Баз ты вобще сам то знаешь что те нужно

Чем это решение из вчерашнего примера непоходит ?
00 00 1101 0111 0010 0101 0010 0101 1101
00 11 1101 0111 0010 0101 0101 0101 1001
00 00 1101 0100 0010 0101 0010 0101 1111
00 10 1101 0101 0010 0101 0010 0101 0010

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

Что приоретенее длина блока или количество повторений?
...
Рейтинг: 0 / 0
04.01.2013, 00:58
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099766
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
ДохтаР2 битный блоки с 3 уникальными значениями, или 2 битные с 3 уникальными значениями ?


Наверное ты имел ввиду
2 битные блоки с 3 мя уникальными значениями. Или 3х битные с 4мя уникальными.
Тут правило простое, приоритет имеет тот блок у которого больше всего уникальных значений. Потом идет размер блока. Чем меньше, тем лучше.
...
Рейтинг: 0 / 0
04.01.2013, 00:59
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099768
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BAZlSTmaytonпропущено...

Там нету кодирования минут. Только целые дни. Первоисточник по формату ИНН здесь
http://zliypes.com.ua/blog/2007/10/29/ukrainian-pti/

тогда точно сжатие может составить 32 раза.
Каждый день ктото рождался и дату рождения каждого следующего ребенка кодируй 0, если его дата не отличается от преведущей даты рождения, и 1 если отличаеатся на один день.
Акей. Мне нужна числовая оценка. Сколько КБ/Мb будет
занимать структура данных (хеш-тейбла, tree-мапа или еще хер знаеть какая
биткарта). Мне нужно знать укладывается ли она в память мобильного
приложения и в память JavaScript-машины браузера.

Сейчас ползаю по сайту http://www.ukrstat.gov.ua/ но там только
общая статистика. А мне нужна рождаемость по дням.
...
Рейтинг: 0 / 0
04.01.2013, 01:00
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099769
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
BAZlSTДохтаР2 битный блоки с 3 уникальными значениями, или 2 битные с 3 уникальными значениями ?


Наверное ты имел ввиду
2 битные блоки с 3 мя уникальными значениями. Или 3х битные с 4мя уникальными.
Тут правило простое, приоритет имеет тот блок у которого больше всего уникальных значений. Потом идет размер блока. Чем меньше, тем лучше.

я имел ввиду 2 битные с 3-мя уникальными,
и 3 бинтые с 3-мя уникальными.
...
Рейтинг: 0 / 0
04.01.2013, 01:02
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099771
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BAZlST1. Где приращение "i" ?
2. Программа должна выводить два числа. Смещение слева и размер блока бит.
Ну вот зачем придираешся? Идея то ведь внутри цикла уже развернута.
Что там еще добавить єто уже мелочи.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
...
i=0;
Amin=0x0000 0000;
Amax=0xFFFF FFFF;
while(i<N){
   Amin = Amin OR A(i);
   Amax = Amax AND A(i);
   i++;
}
Axor=Amin XOR Amax;
print("Offset = %d, Length=%d",_offset(Axor),_length(Axor));


Тестируй и говори где какие баги и тайминги.
...
Рейтинг: 0 / 0
04.01.2013, 01:04
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099772
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
maytonBAZlSTпропущено...


тогда точно сжатие может составить 32 раза.
Каждый день ктото рождался и дату рождения каждого следующего ребенка кодируй 0, если его дата не отличается от преведущей даты рождения, и 1 если отличаеатся на один день.
Акей. Мне нужна числовая оценка. Сколько КБ/Мb будет
занимать структура данных (хеш-тейбла, tree-мапа или еще хер знаеть какая
биткарта). Мне нужно знать укладывается ли она в память мобильного
приложения и в память JavaScript-машины браузера.

Сейчас ползаю по сайту http://www.ukrstat.gov.ua/ но там только
общая статистика. А мне нужна рождаемость по дням.

Очевидно что так сжать удасться только первые 5 цифер ИНН, где дата рождения.
Очевидно также что не о какой хештейбле и три мапе речь не идет, поскольку это фактически заархивированая твоя последовательность. Единственый поиск по такой последовательности - фулскан.
...
Рейтинг: 0 / 0
04.01.2013, 01:04
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099774
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
maytonBAZlST1. Где приращение "i" ?
2. Программа должна выводить два числа. Смещение слева и размер блока бит.
Ну вот зачем придираешся? Идея то ведь внутри цикла уже развернута.
Что там еще добавить єто уже мелочи.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
...
i=0;
Amin=0x0000 0000;
Amax=0xFFFF FFFF;
while(i<N){
   Amin = Amin OR A(i);
   Amax = Amax AND A(i);
   i++;
}
Axor=Amin XOR Amax;
print("Offset = %d, Length=%d",_offset(Axor),_length(Axor));


Тестируй и говори где какие баги и тайминги.

Что делают эти функции, покажи на нескольких примерах ?
_offset(Axor),_length(Axor)
...
Рейтинг: 0 / 0
04.01.2013, 01:05
| Ответить | Цитировать | Написать  
Лучшие задачи проекта
    #38099782
BAZlST
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
BAZlST
Участник
ДохтаРBAZlSTпропущено...


Наверное ты имел ввиду
2 битные блоки с 3 мя уникальными значениями. Или 3х битные с 4мя уникальными.
Тут правило простое, приоритет имеет тот блок у которого больше всего уникальных значений. Потом идет размер блока. Чем меньше, тем лучше.

я имел ввиду 2 битные с 3-мя уникальными,
и 3 бинтые с 3-мя уникальными.

тогда двух битные имеют приоритет, поскольку они короче чем трехбитные блоки.
...
Рейтинг: 0 / 0
04.01.2013, 01:21
| Ответить | Цитировать | Написать  
25 сообщений из 191, страница 5 из 8
  5  все
Форумы / Другие СУБД [игнор отключен] [закрыт для гостей] / Лучшие задачи проекта
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=56&msg=38099744&tid=2015281]:
 0ms
get settings:
 9ms
get forum list:
 12ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 48ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 232ms
total:  377ms
созд. / загр.: 377ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]