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

Задача на одномерный массив - C++

Восстановить пароль Регистрация
 
Harutyunyan
1 / 1 / 0
Регистрация: 28.09.2012
Сообщений: 91
17.03.2013, 22:25     Задача на одномерный массив #1
Дана задача: "Лесенка"
Кликните здесь для просмотра всего текста

Вова стоит перед лесенкой из N ступеней. На каждой из ступеней написаны произвольные целые числа. Первым шагом Вова может перейти на первую ступень или, перепрыгнув через первую, сразу оказаться на второй. Также он поступает и дальше, пока не достигнет N-ой ступени. Посчитаем сумму всех чисел, написанных на ступенях через которые прошел Вова.

Требуется написать программу, которая определит оптимальный маршрут Вовы, при котором, шагая, он получит наибольшую сумму.

Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число N – количество ступеней лестницы. Во второй строке через пробел заданы числа, написанные на ступенях лестницы, начиная с первой. Количество ступеней не превышает 1000, числа, написанные на ступенях, не превосходят по модулю 1000.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать в первой строке наибольшее значение суммы. Во второй строке должны быть записаны через пробел номера ступеней по возрастанию, по которым должен шагать Вова.

Примеры:
Код
INPUT.TXT	             OUTPUT.TXT
Пример 1:
3                              4
1 2 1                         1 2 3
	                               

Пример 2:
3                              2
1 -1 1                       1 3


Я ее решаю таким образом:
Кликните здесь для просмотра всего текста

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 <fstream> 
 
int A[1001], B[1001], N, S, i, j, p;
 
int main()
{ 
    std::fstream I("input.txt"), O("output.txt", 2); 
    for(I >> N; I >> A[i++];);
    for(i = 0; i < N - 1; i++)
    {
        if(A[i] < 0 && 0 > A[i + 1])
        {
            if(A[i] > A[i + 1])
                B[i] = i + 1, S += A[i], p++;
            else
                B[i] = i + 2, S += A[i], p++;
        }
        if(A[i] < 0 && A[i + 1] > 0)
            B[i] = i + 2, S += A[i + 1], p++;
 
        if(A[i] > 0 && A[i + 1] < 0)
            B[i] = i + 1, S += A[i], p++;
 
        if(A[i] > 0 && 0 < A[i + 1])
            B[i] = i + 1, S += A[i], p++;
    }
    O << S << "\n";
    for(i = 0; i <= p; i++)
        O << B[i] << " ";
}


Но решение не совсем правильно.

Как решить данную задачу?

Не по теме:


Вот ссылка на задачу: ********/index.asp?main=task&id_task=329
Модераторы, источник проверяный!

Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2013, 22:25     Задача на одномерный массив
Посмотрите здесь:

C++ Задача на одномерный массив)
C++ ЗАДАЧА НА ОДНОМЕРНЫЙ МАССИВ
C++ Задача по С++ на одномерный массив
C++ Задача на одномерный массив
C++ Задача на одномерный массив
C++ задача на с++( одномерный массив)
задача по C++( одномерный массив) C++
C++ Задача на одномерный массив

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.03.2013, 23:55     Задача на одномерный массив #2
Цитата Сообщение от Harutyunyan Посмотреть сообщение
Но решение не совсем правильно.
см комментарии:
Цитата Сообщение от Harutyunyan Посмотреть сообщение
C++
1
2
3
4
5
6
7
if(A[i] < 0 && 0 > A[i + 1])
 {
 if(A[i] > A[i + 1])
 B[i] = i + 1, S += A[i], p++;
 else
 B[i] = i + 2, S += A[i], p++;// в этой строке видимо опечатка, должно быть S +=A[i+1]
 }
Цитата Сообщение от Harutyunyan Посмотреть сообщение
C++
1
2
if(A[i] > 0 && 0 < A[i + 1])
 B[i] = i + 1, S += A[i], p++;// а для этого случая не учитывается вообще что больше A[i] или A[i+1]
И еще одно упущение: если есть нули и оптимальный путь будет проходить по ним, то это вообще в коде не учитывается (нет ни одного условия, когда A[i] и A[i+1] могут быть равными 0)
Yandex
Объявления
17.03.2013, 23:55     Задача на одномерный массив
Ответ Создать тему
Опции темы

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