Форум программистов, компьютерный форум CyberForum.ru

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

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

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

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

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

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

пример
3
1 2 3
ответ 4
Миниатюры
Платная лестница  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2013, 00:30     Платная лестница
Посмотрите здесь:

Лестница Pascal
C++ лестница
Pascal Олимпиадная задача. Лестница из кубиков.
лестница у воды
Платная подписка Joomla
AVR Платная ли Atmel Studio?
Turbo Pascal Лестница
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 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 минуты
я так понимаю что ето задание основа "Платная лестница"
BumerangSP
4284 / 1406 / 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;
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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}
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
10.11.2013, 14:30  [ТС]     Платная лестница #5
BumerangSP, а можете написать комент к 4,5 строке кода?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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].
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 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");
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.11.2013, 14:51     Платная лестница #8
newyork7776, в формуле, которую я привел, неявно предполагалось, что ступеньки индексируются с 1, а у вас с 0. в остальном вроде все ок, только вы в конце выводите несуществующую ячейку из-за, опять же, несогласованности индексов.
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 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]
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.11.2013, 14:55     Платная лестница #10
newyork7776, я не понимаю вообще, как это работает. у вас массив ans[] не объявлен.
Крюгер
0 / 60 / 3
Регистрация: 16.11.2012
Сообщений: 418
Записей в блоге: 3
10.11.2013, 14:58     Платная лестница #11
newyork7776,

Не по теме:

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

newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 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");
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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;
}
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 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 правельно
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.11.2013, 15:06     Платная лестница #15
вроде все хорошо, кроме этой строки if (i==1) {ans[i]=v[i]+ans[i-1];}; нет смысла платить за нулевую ступеньку, когда можно перепрыгнуть через нее.
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
10.11.2013, 15:07  [ТС]     Платная лестница #16
а если n==1?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.11.2013, 15:10     Платная лестница #17
Цитата Сообщение от newyork7776 Посмотреть сообщение
а если n==1?
то вы сразу прыгаете на первую ступеньку, и все хорошо. у вас числа все натуральные, следовательно добавление любого лишнего шага к оптимальному пути будет вести к тому, что он станет совсем не оптимальным.
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
10.11.2013, 15:17  [ТС]     Платная лестница #18
Кликните здесь для просмотра всего текста
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;
    cin >> n;
    if (n!=0){
    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 <<ans[n-1] << "\n";}
}

вот я кидаю свой код на сайт вот задание

Добавлено через 38 секунд
Кликните здесь для просмотра всего текста
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;
    cin >> n;
    if (n!=0){
    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 <<ans[n-1] << "\n";}
}

результат
Тест Статус Время работы Астрономическое время работы Используемая память
1 Неправильный ответ 0 0.017 1306624
2 OK 0 0.019
3 Неправильный ответ 0 0.003 4096
4 Неправильный ответ 0 0.004 4096
5 Неправильный ответ 0.004 0.004 4096
6 OK 0.004 0.004 4096
7 OK 0 0.003 4096
8 Неправильный ответ 0 0.004 4096
9 Неправильный ответ 0 0.003 4096
10 Неправильный ответ 0.004 0.021 1298432
11 OK 0 0.011 4096
12 OK 0 0.004 4096
13 Неправильный ответ 0.004 0.004 4096
14 Неправильный ответ 0.004 0.003 4096

Добавлено через 2 минуты
1
Кликните здесь для просмотра всего текста
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 <iostream>
#include <vector>
using namespace std;
 
int 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);
    }
 
    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";
}
Кликните здесь для просмотра всего текста
Тест Статус Время работы Астрономическое время работы Используемая память
1 Неправильный ответ 0 0.003 1306624
2 Неправильный ответ 0 0.003 1306624
3 Неправильный ответ 0 0.003 1306624
4 Неправильный ответ 0 0.004 1306624
5 Неправильный ответ 0.004 0.004 1298432
6 Неправильный ответ 0.004 0.004 1306624
7 Неправильный ответ 0 0.004 1306624
8 Неправильный ответ 0 0.004 1306624
9 Неправильный ответ 0 0.004 1306624
10 OK 0.004 0.003 1298432
11 OK 0 0.004 1306624
12 OK 0.004 0.004 1306624
13 Неправильный ответ 0.004 0.003 1306624
14 Неправильный ответ 0 0.003 1306624

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
using namespace std;
 
int 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 минуту
я уже много вариантов перепробовал но результата не найшол
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.11.2013, 15:19     Платная лестница #19
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.11.2013, 15:21     Платная лестница
Еще ссылки по теме:

Определить сколькими различными способами можно подняться на заданную ступеньку (Лестница в Небо) C++
Платная IDE Basic
OpenGL GlMaterial c GL_SPECULAR проявляет артефакты (лестница)

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

Или воспользуйтесь поиском по форуму:
newyork7776
347 / 340 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
10.11.2013, 15:21  [ТС]     Платная лестница #20
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
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] = minimalne(ans[i-1], ans[i-2]) + cost[i];
    cout << ans[n-1] << endl;
    return 0;
}
Кликните здесь для просмотра всего текста
Тест Статус Время работы Астрономическое время работы Используемая память
1 Неправильный ответ 0 0.017 1306624
2 OK 0 0.019
3 Неправильный ответ 0 0.003 4096
4 Неправильный ответ 0 0.004 4096
5 Неправильный ответ 0.004 0.004 4096
6 OK 0.004 0.004 4096
7 OK 0 0.003 4096
8 Неправильный ответ 0 0.004 4096
9 Неправильный ответ 0 0.003 4096
10 Неправильный ответ 0.004 0.021 1298432
11 OK 0 0.011 4096
12 OK 0 0.004 4096
13 OK 0.004 0.004 4096
14 Неправильный ответ 0.004 0.003 4096
Yandex
Объявления
10.11.2013, 15:21     Платная лестница
Ответ Создать тему
Опции темы

Текущее время: 16:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru