Форум программистов, компьютерный форум, киберфорум
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 29, средняя оценка - 4.90
jds_07
28 / 27 / 1
Регистрация: 12.03.2009
Сообщений: 85
#1

Задача Компьютерная игра C++ - C++

08.09.2009, 14:49. Просмотров 3967. Ответов 20
Метки нет (Все метки)

Здравствуйте!

Помогите решить задачку на тему Динамическое программирование.
У меня проходит только 5-тестов.
Задача находится здесь:

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.09.2009, 14:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача Компьютерная игра C++ (C++):

Компьютерная графика на VS C++ MFC. Срочно требуется помощь! - C++
Привет всем. Я с 3 курса факультета информационных технологий НГУ. Хочу попросить помощи в решении задач по курсу комп. графики....

компьютерная графика - C++ Builder
нужно реализовать вот такое задание: Выдача на экран изображения с эффектами. В качестве изображения берется файл в графическом формате...

Компьютерная графика - C++ Builder
Не могу реализовать задачу, в которой нужно изобразить движение солнца по схеме: утро-восход, день - в зените (максимальная яркость), вечер...

Компьютерная графика на C++ Builder - C++ Builder
Вот с этим нужно что бы получилось ниже указанное, что бы внутри буквы была закраска только#include <stdio.h> #include <conio.h> ...

Как сделать так, чтобы при нажатии на кнопку "Новая игра" игра начиналась заново? - C++ Builder
Как сделать так, чтобы при нажатии на кнопку "Новая игра" игра начиналась заново? unit1.cpp void __fastcall TForm1::N1Click(TObject...

Компьютерная графика: смоделировать период жизни яблони от весны (цветение) до осени (сбор урожая) - C++ Builder
Здравствуйте, не могу реализовать задачу, в которой нужно смоделировать период жизни яблони от весны (цветение) до осени (сбор урожая)....

20
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
08.09.2009, 15:34 #2
А где там 5 тестов ?
Там только два теста.
Задача решается тривиально.
Нужно начать вычислять минимальное кол-во энергии справа налево.
Пусть высота платформы задается в массиве height[].
Сначала массив energy[] на N значений пустой.
Потом заполняем N-тое значение, потом N-1, потом N-2.
И когда дойдем до 1-ого значения - это и будет искомый результат.

Пусть мы находимся на I-ом шаге - то есть нам нужно заполнить ячейку I.
Все ячейки справа - от I+1 до N уже заполнены.
Все ячейки слева - от 1 до I-1 незаполнены.
С нашего места у нас есть два варианта действий.
1) Сделать прыжок на I+1 ячейку. В этом случае мы потратим энергию на прыжок, а для I+1 платформы у нас уже есть минимальный ответ - он записан в ячейке I+1.
2) Сделать суперпрыжок на I+2 ячейку.
Тут опять же прыжок, а для I+2 ячейки есть ответ.
Нужно вычислать какой из этих двух вариантов эффективнее и именно это значение записать в ячейку I.
Далее I-- и опять переходим на начало алгоритма.

Ответ будет в energy[1].

А по тексту самой задачи - чего-то бредят они - с чего это вдруг переход на платформу ниже требует затрат энергии ? На платформу выше нужно прыгать, а на платформу ниже нужно падать - затрат либо нет вообще, либо энергия только прибавляется.
0
jds_07
28 / 27 / 1
Регистрация: 12.03.2009
Сообщений: 85
08.09.2009, 15:40  [ТС] #3
Я так и решал. Но 5-й тест не проходит.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <fstream>
#include <math.h>
#include <assert.h>
using namespace std;
 
const int MaxN = 30000;
 
int a[MaxN];
int n, s, t;
 
ifstream fin("input.txt");
ofstream fout("output.txt");
 
int main()
{
    fin >> n;
    assert(1 <= n && n <= MaxN);
    a[0] = MaxN;
    for (int i = 1; i <= n; ++i)
        fin >> a[i];
 
    s = MaxN;
    for (int i = n - 1; i > 1; --i)
    {
        if (abs(a[i] - a[i - 1]) <= abs(a[i] - a[i - 2]) * 3))
        {
            s += abs(a[i] - a[i - 1]);
        }
        else
        {
                                      s += abs(a[i] - a[i - 2]) * 3);
        }
    }
 
    fout << s << endl;
    return 0;
}
0
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
08.09.2009, 16:01 #4
Потому что неправильно решил.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <fstream>
#include <assert.h>
 
using namespace std;
 
const int MAX_N= 30000;
 
int calc_min_energy( int n, int *height );
 
int main( void ) {
 
int i, n, min_energy;
int height[MAX_N];
ifstream fin;
ofstream fout;
 
 
fin.open( "INPUT.TXT" );
fin >>n;
assert( 1<=n && n<=MAX_N );
for ( i= 1; i<=n; i++ ) { fin >>height[i]; }
fin.close();
 
min_energy= calc_min_energy( n, height );
 
fout.open( "OUTPUT.TXT" );
fout <<min_energy <<endl;
fout.close();
 
return 0;
 
} // main()
 
 
int calc_min_energy( int n, int *height ) {
 
int i, var0, var1;
int energy[MAX_N+1];
 
 
energy[n]= 0; energy[n+1]= 0;
for ( i= n-1; i>=1; i-- ) {
    var0= abs( height[i]-height[i+1] )+energy[i+1];
    var1= 3*abs( height[i]-height[i+2] )+energy[i+2];
    energy[i]= (var0<var1) ? var0 : var1;
}
 
return energy[1];
 
} // calc_min_energy()
0
jds_07
28 / 27 / 1
Регистрация: 12.03.2009
Сообщений: 85
08.09.2009, 16:11  [ТС] #5
Цитата Сообщение от odip Посмотреть сообщение
Потому что неправильно решил.
Сам хотя бы тестировал?
Протестируй на это:
3
1 5 10
Ответ 9;
10
3 4 8 10 1 7 1 10 12 15
Ответ 30;
0
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
08.09.2009, 16:22 #6
Сам хотя бы тестировал?
Да

Правильно работает

Добавлено через 1 минуту
На этом сайте 500 задач !
И есть целых три человека, которые решили все 500 задач

Добавлено через 3 минуты
А ты там сколько уже задач решил и какой рейтинг набрал ?

Добавлено через 1 минуту
А все - нашел:

Добавлено через 1 минуту
Пойти зарегистрироваться что-ли и сдать 29-ую задачу

Добавлено через 3 минуты
Главная ошибка у тебя - нужно завести второй массив для найденного уровня минимальной энергии.
Заметил еще несколько мелких, из-за которых тоже считать не будет
1
jds_07
28 / 27 / 1
Регистрация: 12.03.2009
Сообщений: 85
08.09.2009, 16:27  [ТС] #7
Рейтинг 1047. 42 задач решил. С динамикой проблема. В ******** я JDS.
Давай заходи решай под каким именем будешь заходить?
Если что давай вместе обсуждать задачки. Кстати твоя прога не проходит 7-й тест. Сам проверь если не веришь. Я там еще условие добавил при n = 1. Ответ 1-ый элемент.
0
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
08.09.2009, 16:40 #8
Если что давай вместе обсуждать задачки.
Тут на форуме ?
Кстати твоя прога не проходит 7-й тест.
А какую ошибку пишет ?
Я там еще условие добавил при n = 1. Ответ 1-ый элемент.
При n=1 никуда прыгать не нужно. Ответ 0.
Программа выводит 0.

Добавлено через 4 минуты
Если ответ - первый элемент, тогда организаторы задач мягко говоря неумные люди.
Условие задачи: "Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней? "
Если платформа одна, то первая платформа и есть последняя. Прыгать никуда не нужно.
Ответ - 0.
Если же они считают что нужно прыгать на первую платформу снизу или c последней платформы вниз, тогда приведенные в качестве теста варианты потому что они там не прыгают !

Добавлено через 2 минуты
Я к ним на форум зашел по 29-ой задаче.
Там все ругаются на этот 7-ой тест.
Вообщем коряво они его составили
0
jds_07
28 / 27 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 14:53  [ТС] #9
Нашел контрпример на 7-й тест

5
1 0 1 0 5

ответ: 6
0
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 16:20 #10
Какой еще контр-пример ?
Условие задачи прочитай:
В первой строке входного файла INPUT.TXT записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 – высоты, на которых располагаются платформы.

Высота платформы - НАТУРАЛЬНОЕ ЧИСЛО, то есть от 1 и выше.
0
jds_07
28 / 27 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 16:22  [ТС] #11
Ты сперва запусти под этот тест свою прогу. Если выведет 6 то твоя прога пройдет все тесты.
0
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 16:31 #12
Не проходит.

Добавлено через 1 минуту
Но и тест условию задачи не соответствует.
Я там порешал задачи - у них там такие косяки очень редко, но есть.
Хотя конечно в программе тоже ошибка есть
0
jds_07
28 / 27 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 16:33  [ТС] #13
Народ решил значит и мы должны решить!
0
odip
Эксперт С++
7161 / 3223 / 58
Регистрация: 17.06.2009
Сообщений: 14,164
11.09.2009, 16:40 #14
Я тут думал как написать программу которая выуживает от них все тесты
Похоже у них задачи компилируются Visual Studio, а не gcc.
Можно написать сетевую программу, которая посылает все файлы INPUT.TXT по сети.
Правда для этого придется решить все задачи

Добавлено через 30 секунд
Я там уже штук 30 задач решил.
0
jds_07
28 / 27 / 1
Регистрация: 12.03.2009
Сообщений: 85
11.09.2009, 16:53  [ТС] #15
а остальные когда будешь решать?

Добавлено через 3 минуты
Кстати ты сам откуда, сколько тебе лет, где учился?
0
11.09.2009, 16:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.09.2009, 16:53
Привет! Вот еще темы с ответами:

Компьютерная графика - Visual C++
Может кто-нибудь объяснит модели освящения подробно(а именно диффузную),и как её связать с методом Гуро. Добавлено через 4 минуты Я...

Как сделать преграды?[Компьютерная графика] - Visual C++
Может вопрос не по теме, но не знаю куда писать Как сделать преграды, то есть чтобы не выходить за пределы карты например? не пойму...

Си++ и компьютерная графика. Лекции и практикум по программированию на Си++ - Visual C++
Есть книга (чистая и новая): Андрей Богуславский Си++ и компьютерная графика. Лекции и практикум по программированию на Си++ ...

Компьютерная игра (платформы) - C++
Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru