На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Поиск Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> 10 максимальных элементов
Rembo99
Сообщ. #1 ,
    Unregistered
    Кто подскажет.
    Есть массив больше 2000 положительных чисел.

    Как определить первые десять максимальных чисел.
    wormball
    Сообщ. #2 ,
      Unregistered
      сколько дней назад с программированием познакомился?? ;D
      заводишь массив из 10 чисел, записываешь туда нули. просматриваешь большой массив по порядку, если какое либо число в малом массиве меньше текущего числа, записываешь на его место таковое число.

      vot и всё ;D
      Сообщение отредактировано: wormball -
      Black Star
      Сообщ. #3 ,

        Master
        ******
        Профиль · PM
        Поощрения: 14 Dgm
        Рейтинг (т): 99
        Цитата
        заводишь массив из 10 чисел, записываешь туда нули


        :( Не пойдет... по одно простой причине :)
        Есть вероятность, что все числа отрицательные :)
        Закидывать надо не нули, а 1е число из проверяемых!
        wormball
        Сообщ. #4 ,
          Unregistered
          Цитата Black_Star, 05.09.03, 20:55:35
          Есть вероятность, что все числа отрицательные :)

          Цитата Rembo99, 05.09.03, 14:06:45
          Есть массив больше 2000 положительных чисел.

          ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D
          Black Star
          Сообщ. #5 ,

            Master
            ******
            Профиль · PM
            Поощрения: 14 Dgm
            Рейтинг (т): 99
            :) Sorry невнимательно прочитал...
            wormball
            Сообщ. #6 ,
              Unregistered
              Цитата Black_Star, 06.09.03, 02:56:47
              :) Sorry невнимательно прочитал...

              твоя невнимательность куда более велика, чем ты думаешь. алгоритм-то неправильный! число надо записывать не просто на место любого числа, его меньшего, а на место наименьшего из 10ти чисел, иначе получится глупость.
              PAV
              Сообщ. #7 ,
                Member
                **
                Профиль · PM
                Рейтинг (т): 13
                Цитата wormball, 08.09.03, 15:25:44

                число надо записывать не просто на место любого числа, его меньшего, а на место наименьшего из 10ти чисел.

                Медленно, но верно движемся в сторону сортировки :)
                wormball
                Сообщ. #8 ,
                  Unregistered
                  да, но сортировать большой массив не имеет смысла, ведь тогда будет сложность n ln n, а так сложность просто n. можно, конечно, рассортировать маленький массив, а потом старательно поддерживать его в отсортированном состоянии, но я думаю, что так будет ничуть не быстрее.
                  esperanto
                  Сообщ. #9 ,

                    математик
                    *****
                    Профиль · PM
                    Поощрения: 5 Dgm
                    Рейтинг (т): 50
                    И так правильный ответ   О(п).


                    1) порядковые статистики алгоритм который позволяет найти любой порядковый эл-т
                    (мин-й или втор-й мин-й или средний и т.п) за О(п)


                    2) Применить в цикле 10 раз


                    ВСе
                    wormball
                    Сообщ. #10 ,
                      Unregistered
                      повремени также (в смысле считаться будет за такое же время)
                      Black Star
                      Сообщ. #11 ,

                        Master
                        ******
                        Профиль · PM
                        Поощрения: 14 Dgm
                        Рейтинг (т): 99
                        Цитата
                        твоя невнимательность куда более велика, чем ты думаешь


                        Плохой ты :(
                        Black Star
                        Сообщ. #12 ,

                          Master
                          ******
                          Профиль · PM
                          Поощрения: 14 Dgm
                          Рейтинг (т): 99
                          А заполнить маленький массив просто...
                          S(2000)
                          M(10)
                          X:=1:X2:=1
                          m(x):=max(s(i))
                          x:=x+x2
                          if x>9 or x<2 then x2:=-x2
                          и т.д...
                          В вопросе нет указаний, чтобы они шли в порядке возрастания...
                          esperanto
                          Сообщ. #13 ,

                            математик
                            *****
                            Профиль · PM
                            Поощрения: 5 Dgm
                            Рейтинг (т): 50
                            Вот еще решение

                            1) строим кучу   0(п)
                            2) удаляем 10 раз макс-элемент 0(лог(п))

                            -------------
                            0(п)

                            и замечу не нужна дополнительная память
                            Trurl
                            Сообщ. #14 ,
                              Junior
                              *
                              Профиль · PM
                              Рейтинг (т): 0
                              Начинаем сортировку вставками и завершаем после 1 прохода
                              Сообщение отредактировано: Trurl -
                              esperanto
                              Сообщ. #15 ,

                                математик
                                *****
                                Профиль · PM
                                Поощрения: 5 Dgm
                                Рейтинг (т): 50
                                Цитата Trurl, 10.09.03, 16:44:04
                                Начинаем сортировку вставками и завершаем после 1 прохода



                                какой проход в сортировке ставками и почему после первого и какова сложность и кажись не правильно
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (2) [1] 2  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0.0910 ]   [ 15 queries used ]   [ Generated: 24.10.26, 23:47 GMT ]  
                                Powered by Invision Power Board(U) v1.2 © 2003  IPS, Inc.