crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

2 страниц V  < 1 2  
Ответить в данную темуНачать новую тему
> Вода между стен, забавный тест от программистов твиттера
ilyabvt
  опции профиля:
сообщение 18.5.2014, 18:40
Сообщение #11


Активный участник
***

Группа: Участник
Сообщений: 297
Регистрация: 23.6.2011
Пользователь №: 2765

Спасибо сказали: 45 раз(а)




Репутация:   3  


Цитата
а для { 3, 1, 2, 1, 4, 1, 2, 1, 4 } неправильно считает.

Обновил код, теперь правильно:
Раскрывающийся текст
int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, middle, level;

    if (count < 3) { return 0; }

    for (left=0;  left<count-1;  ++left) {
        if (x[left+1] < x[left]) { break; }
    }
    for (right=count-1;  right>=1;  --right) {
        if (x[right-1] < x[right]) { break; }
    }

    while (left < right) {
        for (middle=left+1;  middle<right;  ++middle) {
            if (x[middle] >= x[left]) { break; }
        }
        level = std::min(x[left], x[middle]);   //min на случай middle==right
        for (int i=left; i<middle; ++i) {
            if (level-x[i] > 0) { result += level-x[i]; }
        }
        left = middle;
    }

    return result;
}
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 19.5.2014, 19:31
Сообщение #12


Профессионал
*****

Группа: Модератор
Сообщений: 1593
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


Цитата(Алексей1153 @ 18.5.2014, 14:28) *
Iron Bug, а вчера абсолютно внезапно посетил твой город :D Симпатичный город. Но равнина (это я о ландшафте) непривычная, конечно, для глаза

да уж где тут равнина? почти все улицы вверх или вниз идут :) уральские горы, однако. конечно, не Кавказ, но и равниной назвать трудно.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Iron Bug
  опции профиля:
сообщение 19.5.2014, 20:07
Сообщение #13


Профессионал
*****

Группа: Модератор
Сообщений: 1593
Регистрация: 6.2.2009
Из: Yekaterinburg
Пользователь №: 533

Спасибо сказали: 218 раз(а)




Репутация:   12  


Цитата(ilyabvt @ 18.5.2014, 21:40) *
Обновил код, теперь правильно:

обновляй ещё:
{ 2, 4, 4, 0, 0, 3, 0, 1, 2 } :)
я тупо сделала генерацию случайных последовательностей и сравниваю. если результаты разных алгоритмов разные - проверяю вручную.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 20.5.2014, 6:53
Сообщение #14


фрилансер
******

Группа: Участник
Сообщений: 2890
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


Iron Bug, наверное, в самом городе из-за зданий не видать. Но на окраинах - поле поле поле, а там лес. Некуда бечь :D



я ещё алгоритм придумал - пусть некий муравей ползёт через всю стену слева направо. Он запоминает координату (Di), где он начал спускаться вниз. Также он связывает с каждой Di координату Ui, где он шёл вверх и уровень был равен равен или меньше Di. После прохождения всей стены берём все группы D-U и интегрируем пустое место под ними

Можно оптимизировать - группы не собирать, а завершённые интегрировать сразу

Сообщение отредактировал Алексей1153 - 20.5.2014, 6:55
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 20.5.2014, 7:47
Сообщение #15


фрилансер
******

Группа: Участник
Сообщений: 2890
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


ещё оптимизация для муравья - ему не обязательно спускаться на дно ям, он может их переплывать на глубине 1 блок
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ilyabvt
  опции профиля:
сообщение 20.5.2014, 18:24
Сообщение #16


Активный участник
***

Группа: Участник
Сообщений: 297
Регистрация: 23.6.2011
Пользователь №: 2765

Спасибо сказали: 45 раз(а)




Репутация:   3  


Цитата(Iron Bug @ 19.5.2014, 23:07) *
Цитата(ilyabvt @ 18.5.2014, 21:40) *
Обновил код, теперь правильно:

обновляй ещё:
{ 2, 4, 4, 0, 0, 3, 0, 1, 2 } :)
я тупо сделала генерацию случайных последовательностей и сравниваю. если результаты разных алгоритмов разные - проверяю вручную.

Обновил еще :)
На этот раз тоже проверял на случайных последовательностях.
Раскрывающийся текст
int calcWaterVolume(int count, int *x)
{
    int result = 0;
    int left, right, middle, level;

    if (count < 3) { return 0; }

    for (left=0;  left<count-1;  ++left) {
        if (x[left+1] < x[left]) { break; }
    }
    for (right=count-1;  right>=1;  --right) {
        if (x[right-1] < x[right]) { break; }
    }

    while (left < right) {
        for (middle=left+1;  middle < right;  ++middle) {
            if (x[middle] > x[middle-1]  &&  x[middle+1] <= x[middle]) {
                bool needbreakCycle = true;
                for (int i=middle+1; i<=right; ++i) {
                    if (x[i] > x[middle]  &&  x[middle] <= x[left]) {
                        middle = i-1;       //-1 т.к. на каждой итерации ++middle
                        needbreakCycle = false;
                        break;
                    }
                }
                if (needbreakCycle) { break; }
            }
        }
        level = std::min(x[left], x[middle]);   //min на случай middle==right
        for (int i=left; i<middle; ++i) {
            if (level-x[i] > 0) { result += level-x[i]; }
        }
        left = middle;
    }

    return result;
}


Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

2 страниц V  < 1 2
Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 8.12.2019, 19:12