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

Найти отрезок в массиве. - C++

Войти
Регистрация
Восстановить пароль
 
wH3y
0 / 0 / 0
Регистрация: 27.10.2009
Сообщений: 15
06.11.2009, 11:31     Найти отрезок в массиве. #1
Дан массив состоящий из N чисел , найти тот отрезок элементов сумма которого больше 100 .
В массиве могут быть отрицательные числа.

помогите решить пожалуйста)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2009, 11:31     Найти отрезок в массиве.
Посмотрите здесь:

Найти отрезок максимальной длины в массиве А C++
Найти сумму и число тех элементов массива, которые попадают на заданный отрезок C++
C++ Найти сумму и число тех элементов заданного массива X1,X2, … ,Xn, которые попадают на заданный отрезок.
C++ В массиве найти отрезок максимальной длины, в котором первое число равно последнему, второе - предпоследнему и т.д. Напечатать характеристики этого от
Строки. Найти в тексте начальный и конечный отрезок цифрового алфавита C++
Найти самый длинный отрезок C++
Найти в тексте наибольший по длине начальный отрезок цифрового алфавита C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sekt
 Аватар для Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
06.11.2009, 11:44     Найти отрезок в массиве. #2
Если один отрезко то просто:
Находишь максимальный и отталкиваешся от него.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.11.2009, 11:59     Найти отрезок в массиве. #3
Sekt, не факт
2 3 1 1 90 5 3 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
#include <stdlib.h>
#include <iostream.h>
int main()
{
    const int n=10;
    int i, j;
    int mas[n]={33, -12, 45, -10, 30, 100, -100, -120, 80, 90};
    int sum;
    bool fl=false;
  for( i = 0; i<n-1 && fl==false; i++)
  {
      sum=mas[i];
      for( j=i+1; j<n && fl==false; j++)
      {
          sum+=mas[j];
          if(sum>100)
              fl=true;
      }
  }
  cout<<i-1<<"   "<<j-1<<endl;            
        system("pause");
        return 0;
}
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
06.11.2009, 22:06     Найти отрезок в массиве. #4
А в чем собственно задача ?
Берем все элементы массива в качестве ответа и все.
Если превышает 100 - задача решена.
Если не превышает 100, то значит решения нет.
Ketino
8 / 8 / 0
Регистрация: 21.09.2009
Сообщений: 84
06.11.2009, 23:07     Найти отрезок в массиве. #5
Цитата Сообщение от odip Посмотреть сообщение
А в чем собственно задача ?
Берем все элементы массива в качестве ответа и все.
Если превышает 100 - задача решена.
Если не превышает 100, то значит решения нет.
Это при условии, что нет отрицательных чисел.
В противном случае - надо искать.
Rififi
 Аватар для Rififi
2332 / 1047 / 43
Регистрация: 03.05.2009
Сообщений: 2,656
06.11.2009, 23:09     Найти отрезок в массиве. #6
Ketino,

Это при условии, что нет отрицательных чисел.
В противном случае - надо искать.


Берем все положительные элементы массива...
далее по тексту
(:
Ketino
8 / 8 / 0
Регистрация: 21.09.2009
Сообщений: 84
06.11.2009, 23:16     Найти отрезок в массиве. #7
Цитата Сообщение от Rififi Посмотреть сообщение
Берем все положительные элементы массива...
далее по тексту
(:
Лучше так - "Берем массив, у которого первый элемент = 101 ..." ;-)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2009, 21:44     Найти отрезок в массиве.
Еще ссылки по теме:

Найти точку пересечения отрезка и перпендикуляра, опущенного на отрезок из точки C++
C++ Найти наибольший отрезок из совершенных чисел
C++ Найти координаты точки, делящей отрезок в заданном отношении
Найти самый используемый отрезок пути в графе C++
Найти отрезок, лежащий целиком в наибольшем количестве окружностей C++

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

Или воспользуйтесь поиском по форуму:
odip
Эксперт C++
 Аватар для odip
7226 / 3288 / 59
Регистрация: 17.06.2009
Сообщений: 14,165
07.11.2009, 21:44     Найти отрезок в массиве. #8
Ну насчет отрицательных чисел в условии не было сказано, я решил что там все >= 0

Можно просто перебрать все отрезки - O(N^3) действий.
Можно использовать метод динамического программирования и найти за меньшее число действий.
Только остановиться нужно как только нашли сумму > 100.
Yandex
Объявления
07.11.2009, 21:44     Найти отрезок в массиве.
Ответ Создать тему
Опции темы

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