Сейчас 14:40:20 Четверг, 28 марта, 2024 год
[ x ] Главная ⇒ Форум ⇐ RSS Файлы Cтатьи Картинки В о й т и   или   з а р е г и с т р и р о в а т ь с я


[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: PUVer, SirNikolas, Ty3uK  
Форум о Warcraft 3 » Раздел для картостроителей » GUI / Jass » [Вопрос] Самое большое число из массива (Как найти?)
[Вопрос] Самое большое число из массива
[HoBu4oK]Дата: Пятница, 05 Октября 2012, 08:04:34 | Сообщение # 1
4 уровень
Группа: Проверенные
Сообщений: 92
Награды: 0
Репутация: 9
Блокировки:
У меня есть массив с int'ерами, как найти самое большое число из этого массива?
 

Ty3uKДата: Пятница, 05 Октября 2012, 08:17:17 | Сообщение # 2
Группа: Ветераны
Сообщений: 6125
Награды: 2
Репутация: 1617
Блокировки:
гугл:
сортировка пузырьком
гномья сортировка
сортировка расческой


╭∩╮(︶︿︶)╭∩╮
"Ульта Тайда мне в жопу!" © k0fe1n
Статьи: MUI-1|MUI-2|Шрифт
Полезности: JASP|JNGP|Уголок библиотек
 

[HoBu4oK]Дата: Пятница, 05 Октября 2012, 10:05:31 | Сообщение # 3
4 уровень
Группа: Проверенные
Сообщений: 92
Награды: 0
Репутация: 9
Блокировки:
Ty3uK, спасибо за инфу, сделал тему можно закрывать.
 

SirNikolasДата: Пятница, 05 Октября 2012, 13:19:08 | Сообщение # 4
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Ty3uK, тогда уж сортировка выбором. Нужно ведь только найти максимум в массиве.

 

kapa6acvlkДата: Пятница, 05 Октября 2012, 16:36:56 | Сообщение # 5
Группа: Проверенные
Сообщений: 612
Награды: 0
Репутация: 361
Блокировки:
Зачем вообще сортировать массив, если человеку просто надо наибольшее значение? Реализуется одним циклом, одним if'ом.

Добавлено (05 Октября 2012, 16:36:56)
---------------------------------------------
вот тема была, можно сделать по аналогии: http://warcraft3ft.info/forum/60-39817-1



Как говориться, не обязательно есть всю кучу говна, чтобы понять, что она однородна.
© Александр Зорич
 

Ty3uKДата: Пятница, 05 Октября 2012, 17:02:56 | Сообщение # 6
Группа: Ветераны
Сообщений: 6125
Награды: 2
Репутация: 1617
Блокировки:
это будет быстрее последовательного сравнения

╭∩╮(︶︿︶)╭∩╮
"Ульта Тайда мне в жопу!" © k0fe1n
Статьи: MUI-1|MUI-2|Шрифт
Полезности: JASP|JNGP|Уголок библиотек
 

SirNikolasДата: Пятница, 05 Октября 2012, 18:00:48 | Сообщение # 7
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Сортировка будет быстрее нахождения максимума?

 

Ty3uKДата: Пятница, 05 Октября 2012, 18:05:04 | Сообщение # 8
Группа: Ветераны
Сообщений: 6125
Награды: 2
Репутация: 1617
Блокировки:
смотря каким алгоритмом же
или неправ?


╭∩╮(︶︿︶)╭∩╮
"Ульта Тайда мне в жопу!" © k0fe1n
Статьи: MUI-1|MUI-2|Шрифт
Полезности: JASP|JNGP|Уголок библиотек
 

AUДата: Пятница, 05 Октября 2012, 18:40:13 | Сообщение # 9
7 уровень
Группа: Проверенные
Сообщений: 471
Награды: 0
Репутация: 70
Блокировки:
Code

// существует глобальный массив udgInteger

function GetMax takes nothing returns integer // возвращает наибольшее число
    local integer n = 0
    local integer max = 100 // размерность массива
    local integer cur = 0
    loop
     set n = n+1    
     If udgIntegerl[n] > cur then
      set cur = udgReal[n]
     EndIf
     exitwhen n >= max
    endloop
    Return cur
endfunction

function GetMaxId takes nothing returns integer // возвращает  индекс наибольшего числа
    local integer n = 0
    local integer n2 = 0
    local integer max = 100 // размерность массива
    local integer cur = 0
    loop
     set n = n+1    
     If udgIntegerl[n] > cur then
      set cur = udgReal[n]
      set n2 = n
     EndIf
     exitwhen n >= max
    endloop
    Return n2
endfunction


Остаться в живых
стрелялка с мышковым управлением =)


Сообщение отредактировал AU - Пятница, 05 Октября 2012, 18:48:43
 

SirNikolasДата: Пятница, 05 Октября 2012, 18:57:10 | Сообщение # 10
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Code
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int* find_max(int a[ ], unsigned n) {
    int* result = a;
    while (--n)
        if (a[n] > *result)
            result = a + n;
    return result;
}

void bubble_sort(int a[ ], unsigned n) {
    unsigned i, j;
    char f;
    for (j = 0; j < n; j++) {
        f = 1;
        for (i = 1; i < n - j; i++)
            if (a[i] < a[i - 1]) {
                a[i] += a[i - 1];
                a[i - 1] = a[i] - a[i - 1];
                a[i] -= a[i - 1];
                f = 0;
            }
        if (f)
            break;
    }
}

enum { ARR_SIZE = 10000 };

int main() {
    int a[ARR_SIZE];
    int* m;
    unsigned i;
    clock_t c0, c1, c2;
    srand((int)time(NULL));
    for (i = 0; i < ARR_SIZE; i++)
        printf("%d ", a[i] = rand());/*[0..32767]*/
    putchar('\n');
    c0 = clock();
    m = find_max(a, ARR_SIZE);
    c1 = clock();
    bubble_sort(a, ARR_SIZE);
    c2 = clock();
    printf("max = %d\nsorted array:\n", *m);
    for (i = 0; i < ARR_SIZE; i++)
        printf("%d ", a[i]);
    printf("\nc0 = %d\nc1 = %d\nc2 = %d"
        "\nclocks for searching: %d\nclocks for sorting: %d",
        c0, c1, c2, c1 - c0, c2 - c1);
    getchar();
}
Впечатляют цифры?

Даже при десяти элементах c1 - c0 = 0; c2 - c1 = 16.


 

Ty3uKДата: Пятница, 05 Октября 2012, 19:02:43 | Сообщение # 11
Группа: Ветераны
Сообщений: 6125
Награды: 2
Репутация: 1617
Блокировки:
SirNikolas, ты же знаешь - я с алгоритмами не дружу :)
Видимо поэтому херню спорол


╭∩╮(︶︿︶)╭∩╮
"Ульта Тайда мне в жопу!" © k0fe1n
Статьи: MUI-1|MUI-2|Шрифт
Полезности: JASP|JNGP|Уголок библиотек
 

SirNikolasДата: Пятница, 05 Октября 2012, 19:21:31 | Сообщение # 12
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Кстати, надо еще "расческой" попробовать.

Добавлено (05 Октября 2012, 19:21:31)
---------------------------------------------

Code
void comb_sort(int a[ ], unsigned size) {
    unsigned jump = size, i;
    char swapped = 1;
    while (jump > 1 || swapped) {
        if (jump > 1)
            jump = (unsigned)(jump / 1.25);
        swapped = 0;
        for (i = 0; i + jump < size; i++)
            if (a[i] > a[i + jump]) {
                a[i] += a[i + jump];
                a[i + jump] = a[i] - a[i + jump];
                a[i] -= a[i + jump];
                swapped = 1;
            }
    }
}
При ARR_SIZE = 10000:
clocks for searching: 0
clocks for sorting (bubble): 750
clocks for sorting (comb): 16

При ARR_SIZE = 8192:
clocks for searching: 0
clocks for sorting (bubble): 485
clocks for sorting (comb): 15

При ARR_SIZE = 16:
clocks for searching: 0
clocks for sorting (bubble): 0
clocks for sorting (comb): 0

Не знаю, как у меня на 10 получилось 16 пузырьком...

 

Ty3uKДата: Пятница, 05 Октября 2012, 19:24:26 | Сообщение # 13
Группа: Ветераны
Сообщений: 6125
Награды: 2
Репутация: 1617
Блокировки:
SirNikolas, весело :)

╭∩╮(︶︿︶)╭∩╮
"Ульта Тайда мне в жопу!" © k0fe1n
Статьи: MUI-1|MUI-2|Шрифт
Полезности: JASP|JNGP|Уголок библиотек
 

SirNikolasДата: Пятница, 05 Октября 2012, 19:39:12 | Сообщение # 14
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Удалось ускорить пузырьковую сортировку с 0/485/750 до 0/375/563 путем замены
Code
a[i] += a[i - 1];
a[i - 1] = a[i] - a[i - 1];
a[i] -= a[i - 1];
на
Code
t = a[i];
a[i] = a[i - 1];
a[i - 1] = t;
Аналогичные манипуляции с "расческой" заметного выигрыша, понятное дело, не дали.

Добавлено (05 Октября 2012, 19:39:12)
---------------------------------------------
Проверил стандартную функцию C++ std::sort, что из файла <algorithm>. Практически идентична comb_sort.


 

Форум о Warcraft 3 » Раздел для картостроителей » GUI / Jass » [Вопрос] Самое большое число из массива (Как найти?)
  • Страница 1 из 1
  • 1
Поиск:

Copyright © 2006 - 2024 Warcraft3FT.info При копировании материалов c сайта ставьте, пожалуйста, активную обратную ссылку на нас • Design by gReeB04ki ©
Хостинг от uCoz