На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Закрыто esperanto 14-09-2004: задача решена

Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Всех чисел по 2., Одно встречается ровно
    Задача с собечседования по приему на работу.

    Есть массив их N элементов. Всем все числа встречаются два раза, кроме одного оно встречается РОВНО один раз.
    необходимо найти число, встречающееся один раз

    Ограничения:
    - вы можете использовать памяти О(1)
    - быстродействие в наихудшем случае О(N)

    P.S. Я эту задачу решил с подсказкоц и некрасиво.
    P.S.S. Пора мне тоже пополнить данный раздел
    Сообщение отредактировано: esperanto -
      Лю, ты похоже пьян в дрыбадан! ;)
      Путаешься в словах, речь смазана :D
      Слова непонятны.
      А главное: В чём задача-то? :lol:
        решил для случая, когда

        дан массив взаимно простых чисел(пар чисел).


        :wall:
        Microsoft SDE -> Intel algorithmist -> Skype SDET 2
        B.Sc - > M.Sc -> B.Psy -> Scrum Master -> Research Assistent

        https://www.youtube.com/user/igorkle1?feature=mhee
        http://igor-eta.livejournal.com/
        http://www.idea2site.com/
          Я так и не въехал - а чё решать-то?
          Ну есть массив чисел и чё? :blink:
            Цитата DrUnkard @ 13.09.04, 17:28
            Я так и не въехал - а чё решать-то?
            Ну есть массив чисел и чё? :blink:

            условия подправлено
            Microsoft SDE -> Intel algorithmist -> Skype SDET 2
            B.Sc - > M.Sc -> B.Psy -> Scrum Master -> Research Assistent

            https://www.youtube.com/user/igorkle1?feature=mhee
            http://igor-eta.livejournal.com/
            http://www.idea2site.com/
              Цитата
              esperanto, 13.09.04, 22:25
              решил для случая, когда

              дан массив взаимно простых чисел(пар чисел).

              Дан массив int.
              Цитата
              DrUnkard, 13.09.04, 22:06

              Лю, ты похоже пьян в дрыбадан!
              Путаешься в словах, речь смазана
              Слова непонятны.
              А главное: В чём задача-то?

              Я пьян по жизни.
              esperanto уже исправил
                Ага! Ладно, пойду собачку погуляю, заодно и поразмышляю :yes:
                  а скажите про органичение по русски :whistle: :whistle:
                    Цитата

                    а скажите про органичение по русски

                    Количество памяти: постоянно, не зависит от размера массива с числами
                    Число операций: растет пропорционально длине массива, менее по русски(спасибо мех-мату :tong:) Существует константа С такая, что число операций для определения данного числа не превышает C*размер массива.
                      Надо посмотреть конспект по асму, и посмотерть там один из способов очистки регистра, а именно xor eax,eax; Самое интересное - почему он очиститься ;)

                      :whistle: :whistle:
                        Я тоже также думаю, как и POD.
                        Сначала, пока гулял, то первая же пришедшая идея была такой: нужно складывать и вычитать. Одинаковые в конце концов обратятся в ноль, а останется одно непарное число. Но мы не знаем, в какой момент нуно либо вычитать либо прибавлять. И в этом деле нам поможет операция логичекого сложения "ИЛИ", но только "Исключающее ИЛИ".
                        Правильно POD, маладезь! :D

                          1) найти х - самое большое число в массиве

                          2) обозначим через У - минимальное из чисел, таких что У нечетно и 2*У>x

                          3) считаем у*а(1)+у*а(2)+.....у*а(N)=sum

                          4) our number is sum mod y*2

                          пример
                          1 1 2 2 5 5 7
                          х=7
                          у=5
                          сум=10+20+50+7=87
                          our number is 87 mod 10=7





                          Microsoft SDE -> Intel algorithmist -> Skype SDET 2
                          B.Sc - > M.Sc -> B.Psy -> Scrum Master -> Research Assistent

                          https://www.youtube.com/user/igorkle1?feature=mhee
                          http://igor-eta.livejournal.com/
                          http://www.idea2site.com/
                            Esperanto, долго и вобщем-то некрасиво.
                            POD уже дал решение, самое простое. :yes:
                            PS Опередил чертяка! :angry:
                              P.O.D, я человек простой, можно без asma
                                POD наверное имел ввиду:

                                ExpandedWrap disabled
                                   
                                  int res=0;
                                   
                                  for(int i=0;i<n;i++)
                                      res^=mas[i];
                                   
                                  return res;
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Закрыто esperanto 14-09-2004: задача решена



                                Рейтинг@Mail.ru
                                [ Script Execution time: 0,1154 ]   [ 16 queries used ]   [ Generated: 22.07.19, 14:01 GMT ]