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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.79
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,312
Завершенные тесты: 1
#1

Платная лестница - C++

10.11.2013, 00:30. Просмотров 3637. Ответов 27
Метки нет (Все метки)

Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
В первой строке входного файла вводится одно натуральное число N100 — количество ступенек.
В следующей строке вводятся N натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

пример
3
1 2 3
ответ 4
0
Миниатюры
Платная лестница  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2013, 00:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Платная лестница (C++):

лестница - C++
int phi(int n) {int a; a=1; a=2; if (n==1) return a; else a=phi(a+n-1); } как правльно выти из этой рекурсии? алгоритм...

Неправильная лестница на с++ - C++
Нужно сделать лестницу из n-ых элементов чтобы она выгледила вот так : 5 4 5 3 4 5 2 3 4 5 1 2 3 4 5 у меня получилось...

Определить сколькими различными способами можно подняться на заданную ступеньку (Лестница в Небо) - C++
Определить сколькими различными способами можно подняться на десятую ступеньку, если за шаг можно подняться следующую или через одну. Как...

Лестница - Turbo Pascal
Человек поднимается по лестнице один марш которых содержит N ступенек. За один шаг человек может подняться на 1 или 2, или на 3 ... или на...

Лестница - Pascal
Дано натуральное число n.Человек должен подняться по лестнице,имеющей n ступеней.Зная что с каждым шагом он может ступать на каждую ...

Олимпиадная задача. Лестница из кубиков. - Pascal
1) Мальчик Петя строит из кубиков лестницу. Лестница представляет собой несколько стоящихся рядом башенок из кубиков, каждая из которых...

27
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,312
Завершенные тесты: 1
10.11.2013, 13:46  [ТС] #2
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int main()
{
    vector <int> v;
    int s=0,n,k,rez=0;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> k;
        v.push_back(k);
    }
    rez=0;
    for(int i=2;i<n;i++)
    {
        if ((v[i-2]+v[i-1])>(v[i]))
            {
                rez+=v[i];
            }
        if ((v[i-1]+v[i-1])<=(v[i]))
            {
                rez+=(v[i-2]+v[i-1]);
            }
    }
    cout << rez << "\n";
    system("pause");
}


Добавлено через 12 часов 11 минут
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
using namespace std;
 
void main()
{
    
    
    int n;
    int k;
    vector <int> v;
    cin >> n;
    int* MinE = new int[n];
    for(int i=0;i<n;i++)
    {
        cin >> k;
        v.push_back(k);
    }
    if (n>2){
    MinE[0]=0;
    MinE[1]=v[0];
    int E1,E2;
    for (int i=2;i<n;i++)
    {
        E1=(v[i]+v[i-1]);
        E2=(v[i]+v[i-2]);
 
        if (E1+MinE[i-1]<E2+MinE[i-2])
            MinE[i]=E1+MinE[i-1];
        else 
            MinE[i]=E2+MinE[i-2];
    }
 
    cout << MinE[n-1] << "\n";};
    else 
    {
        if (n==1) cout << v[0];
        if (n==2)
        {
            if (v[0]>=v[1]) cout << v[1];
            else cout << v[0];
        }
    }
}


Добавлено через 1 минуту
ответ примерно +,но только когда n<=2 тогда ответ -

Добавлено через 16 секунд
или сам алгоритм кривой =)

Добавлено через 3 минуты
я так понимаю что ето задание основа "Платная лестница"
1
BumerangSP
4287 / 1409 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
10.11.2013, 14:12 #3
Нужно протестить:
C++
1
2
3
4
5
6
const int N = 10;
int sum = 0, a[N] = {1,3, 2, 4, 6, 5, 9, 8, 1, 7};
for (int i = 0; i < N - 1; ++i)
    sum += (a[i] < a[i + 1]) && (i + 1 != N - 1) ? a[i] : a[i++ + 1];
sum += N == 1 ? a[0] : 0;   
cout << "Sum: " << sum << endl;
1
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.11.2013, 14:25 #4
ответ считается динамикой слева-направо. в каждое состояние (каждую ступеньку i) есть переходы из двух предыдущих состояний (ступенек i-1 и i-2). при этом мы утверждаем, что, чтобы оптимально дойти до i-ой ступеньки, нужно оптимально дойти до i-1 и i-2 и выбрать лучший из путей.
тогда решение такое:
http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases} & \text{ if } i == 1 \ || \ i == 2 \ ans[i] = cost[i]\\  & \text{ if } i \ > \ 2 \ ans[i] = min(ans[i-1], \ ans[i-2]) \ + \ cost[i]  \\ \end{cases}
1
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,312
Завершенные тесты: 1
10.11.2013, 14:30  [ТС] #5
BumerangSP, а можете написать комент к 4,5 строке кода?
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.11.2013, 14:31 #6
прошу прощения, не имею работать с редактором формул.
ответ считается динамикой слева-направо.
в каждое состояние (каждую ступеньку i) есть переходы из двух предыдущих состояний (ступенек i-1 и i-2).
при этом мы утверждаем, что, чтобы оптимально дойти до i-ой ступеньки, нужно оптимально дойти до i-1 и i-2, и выбрать лучший из путей.

тогда решение такое:

http://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{cases} & \text{i \leq 2, ans[i] = cost[i]} \\ & \text{i > 2, ans[i] = min(ans[i-1], ans[i-2]) + cost[i]} \end{cases}

где ans[i] - итоговый ответ для ступеньки i, cost[i] - стоимость посещения i-ой ступеньки.

понятно, что ответ на всю задачу - это ans[n].
0
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,312
Завершенные тесты: 1
10.11.2013, 14:47  [ТС] #7
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main()
{
    const int N = 5;
    int sum = 0, a[N] = {1, 1, 1, 1, 1};
    for (int i = 0; i < N - 1; ++i)
        sum += (a[i] < a[i + 1]) && (i + 1 != N - 1) ? a[i] : a[i++ + 1];
    sum += N == 1 ? a[0] : 0;   
    cout << "Sum: " << sum << endl;
    system("pause");
}

должно написать 3 а пишет 2

Добавлено через 13 минут
salam, вот написал но неправельно,или я не то написал
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{   
    vector <int> v;
    int n,k;
    int sum=0;
    cout << "Size = ";cin >>n;
    int* ans = new int[n];
    for(int i=0;i<n;i++)
    {
        cin >> k;
        v.push_back(k);
    }
    for (int i=0;i<n;i++)
    {
        if (i<=2) {ans[i]=v[i];}
        else {ans[i]=minimalne(ans[i-1],ans[i-2])+v[i];}
    }
    cout << "Answer = " << ans[n] << "\n";
    system("pause");
}
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.11.2013, 14:51 #8
newyork7776, в формуле, которую я привел, неявно предполагалось, что ступеньки индексируются с 1, а у вас с 0. в остальном вроде все ок, только вы в конце выводите несуществующую ячейку из-за, опять же, несогласованности индексов.
0
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,312
Завершенные тесты: 1
10.11.2013, 14:53  [ТС] #9
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{   
    vector <int> v;
    int n,k;
    int sum=0;
    cout << "Size = ";cin >>n;
    int* a = new int[n];
    for(int i=0;i<n;i++)
    {
        cin >> k;
        v.push_back(k);
    }
    for (int i=0;i<n;i++)
    {
        if (i<=2) {a[i]=v[i];}
        else {ans[i]=minimalne(ans[i-1],ans[i-2])+v[i];}
    }
    cout << "Answer = " << a[n-1] << "\n";
    system("pause");
}

но результата неправельный,оно запоминает в ответ последнюю ячейку v[n-1]
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.11.2013, 14:55 #10
newyork7776, я не понимаю вообще, как это работает. у вас массив ans[] не объявлен.
0
Крюгер
0 / 60 / 3
Регистрация: 16.11.2012
Сообщений: 431
Записей в блоге: 9
Завершенные тесты: 1
10.11.2013, 14:58 #11
newyork7776,

Не по теме:

не по теме конечно, но у вас слово "лестница" -от слова льстить произошла 0_о ?

0
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,312
Завершенные тесты: 1
10.11.2013, 14:59  [ТС] #12
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{   
    vector <int> v;
    int n,k;
    int sum=0;
    cout << "Size = ";cin >>n;
    int* ans = new int[n];
    for(int i=1;i<=n;i++)
    {   
        ans[i]=0;
        cin >> k;
        v.push_back(k);
    }
    for (int i=1;i<=n;i++)
    {
        if (i<=2) {ans[i]=v[i];}
        else {ans[i]=minimalne(ans[i-1],ans[i-2])+v[i];}
    }
    cout << "Answer = " << ans[n] << "\n";
    system("pause");
}
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.11.2013, 15:03 #13
newyork7776, посмотрите на код, может быть, вам так проще воспринимать.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
    int n;
    cin >> n;
    vector<int> ans(n), cost(n);
    for(int i=0; i < n; ++i)
        cin >> cost[i];
    ans[0] = cost[0];
    ans[1] = cost[1];
    for(int i=2; i < n; ++i)
        ans[i] = min(ans[i-1], ans[i-2]) + cost[i];
    cout << ans[n-1] << endl;
    return 0;
}
0
newyork7776
350 / 343 / 80
Регистрация: 21.05.2013
Сообщений: 1,312
Завершенные тесты: 1
10.11.2013, 15:04  [ТС] #14
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{   
    vector <int> v;
    int n,k;
    int sum=0;
    cout << "Size = ";cin >> n;
    int* ans = new int[n];
    for(int i=0;i<n;i++)
    {   
        ans[i]=0;
        cin >> k;
        v.push_back(k);
    }
    for (int i=0;i<n;i++)
    {
        if (i==0) {ans[i]=v[i];};
        if (i==1) {ans[i]=v[i]+ans[i-1];};
        if (i>1) {ans[i]=minimalne(ans[i-1],ans[i-2])+v[i];};
    }
    cout << "Answer = " << ans[n-1] << "\n";
    system("pause");
}

вот нормальный код програмки,проверте правеольно или нет?
у меня с 3/3 правельно
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
10.11.2013, 15:06 #15
вроде все хорошо, кроме этой строки if (i==1) {ans[i]=v[i]+ans[i-1];}; нет смысла платить за нулевую ступеньку, когда можно перепрыгнуть через нее.
0
10.11.2013, 15:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.11.2013, 15:06
Привет! Вот еще темы с ответами:

GlMaterial c GL_SPECULAR проявляет артефакты (лестница) - OpenGL
OpenGL 1.2 самый обычный, без шейдеров и всяких там расширений. Нарисовал эскиз глобуса, стал экспериментировать с освещением и...

Платная подписка - Joomla
Можно ли сделать платную регистрацию на joomla с ежемесячной оплатой? Какие есть расширения?

Платная IDE - Basic
Здравствуйте. Я тут написал небольшую IDE для FreeBasic'а. IDE удобная и стильная, есть пресеты, подсветка синтаксиса, мультитаб. Сама IDE...

платная регистрация - WordPress
всем привет. в двух словах почему я залез в такие дебри. на сайте работает плагин, который скрывает от незарегистрированных пользователей...


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

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

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