|
|
|
| Здравствуйте, решаю следующую задачу на С++.
В одномерном массиве, состоящем из целых элементов найти сумму элементов, расположенных между первым и последним нулевыми элементами.
Задача распадается на две части: 1) найти нулевые элементы 2) посчитать сумму между ними.
Я вижу два решения. Одно кажется проще, второе должно быть эффективнее, потому что в лучше случае не нужно проходить весь массив от начала до конца.
Дайте, пожалуйста, совет, какой вариант предпочтительнее и почему?
Выявилось различие в работе компиляторов. В среде CodeBloks (компилятор gсс) работают оба кода. В VS C++ 6 работает только первый. Во втором прием барьерного элемента не срабатывает. Никто не знает, почему?
Первый вариант. Без барьерного элемента
#include <iostream>
using namespace std;
int main()
{
const int M = 10;
int i = 0;
int m[M] = {10, 0, -4, -9, 1, 1, 4, 20, -3, -31};
//int m[M] = {-1, 0, 0, 1, 1, 0, 1, 1, 1, 1};
//Вывод массива на экран
for(i = 0; i < M; i++)
cout << m[i] << " ";
//Находим первый и последний нулевые элементы
int zero_b = -1;
int zero_e = -1;
for(i = 0; i < M; i++)
{
if(m[i] == 0)
{
zero_e = i;
if(zero_b == -1)
zero_b = i;
}
}
if(zero_b == -1 && zero_e == -1)
cout << "There is no zero elements\n";
else
{
cout << "Number of first zero element = " << zero_b << endl;
cout << "Number of last zero element = " << zero_e << endl;
}
//Сумма элементов массива, расположенных между 1 и последним нулевыми элементами
int sum = 0;
if(zero_b == -1 && zero_e == -1)
{
return 0;
}
else
{
for(i = zero_b+1; i < zero_e; i++)
{
sum += m[i];
}
cout << "Sum of elements between " << zero_b << " and " << zero_e << " zero elements = " << sum << endl;
}
return 0;
}
|
Второй вариант. С барьерным элементом. Не работает в Вижуал Студио 6. Не срабатывает барьерный элемент, цикл не останавливается
#include <iostream>
using namespace std;
int main()
{
const int M = 10;
int i = 0;
int m[M] = {50, 80, -4, -9, 0, 1, 4, 20, 10, 0};
//Вывод массива на экран
for(i = 0; i < M; i++)
cout << m[i] << " ";
//Находим первый и последний нулевые элементы
int zero_b = 0, zero_e = 0;//первый и последний нулевые элементы
i = 0;
int k = 0;//барьерный элемент
m[M] = k;
cout << "Barrier m[" << M << "] = " << m[M] << endl;
cout << "-------------------\n";
int sum = 0;
while(m[i] != k)
{
i++;
cout << "m[" << i << "] " << " = " << m[i] << endl;
}
if(i == M)
{
cout << "There is no zero elements\n";
}
else
{
zero_b = i;
cout << "Number of first zero element = " << zero_b << endl;
i = M-1;
while(m[i] != 0)//проверяем с обратного конца
i--;
zero_e = i;
cout << "Number of last zero element = " << zero_e << endl;
cout << "-------------------\n";
//Сумма элементов массива, расположенных между 1 и последним нулевыми элементами
if(zero_b == zero_e || abs(zero_b - zero_e) == 1)
cout << "No interval. Sum = " << sum <<endl;
else
{
for(i = zero_b+1; i < zero_e; i++)
{
sum += m[i];
}
cout << "Sum of elements between " << zero_b << " and " << zero_e << " zero elements = " << sum << endl;
}
}
return 0;
}
|
Второй вариант будет очень экономным, если нулевые элементы расположены по концам массива. Но там приходится вводить больше переменных.
P.S. Как можно измерить эффективность работы программы, есть какие-нибудь утилиты, показывающие количество проходов и время, затраченное на них.
Заранее спасибо. | |
|
|
|
|
|
|
|
для: agon
(29.08.2009 в 11:47)
| | Второй вариант ошибочный, так как M у вас имеет значение 10, а элемент m[10] не имеет смысла, так как индексы пробегают значения от 0 до 9. Следовательно, вы обращаетесь к участку памяти, расположенному за пределами массива - поэтому в студии программа и вылетает. Значение m[M] следует заменить на m[M - 1]. | |
|
|
|
|
|
|
|
для: cheops
(30.08.2009 в 12:29)
| | Второй вариант был исправлен следующим образом
#include <iostream>
using namespace std;
int main()
{
const int M = 10;
const int M0 = M+1;//резервируем место для хранения барьерного элемента рядом с основным массивом!
int i = 0;
int k = 0;//барьерный элемент
int m[M0] = {0, 80, -4, -9, 0, 1, 4, 20, 10, 50, 0};//сразу включаем в массив барьерный элемент,
//но впоследствии оперируем массивом M
//Вывод массива на экран
for(i = 0; i < M; i++)
cout << m[i] << " ";
//Находим первый и последний нулевые элементы
int zero_b = 0, zero_e = 0;//первый и последний нулевые элементы
i = 0;
int sum = 0;
while(m[i] != k)
{
i++;
cout << "m[" << i << "] " << " = " << m[i] << endl;
}
if(i == M)
{
cout << "No zero\n";
}
else
{
zero_b = i;
cout << "Number of first zero " << zero_b << endl;
i = M-1;
while(m[i] != 0)//проверяем с обратного конца
i--;
zero_e = i;
cout << "Number of last zero " << zero_e << endl;
cout << "-------------------\n";
//Сумма элементов массива, расположенных между 1 и последним нулевыми элементами
if(zero_b == zero_e || abs(zero_b - zero_e) == 1)
cout << "No interval. Sum = " << sum <<endl;
else
{
for(i = zero_b+1; i < zero_e; i++)
{
sum += m[i];
}
cout << "Sum between " << zero_b << " and " << zero_e << " zero elements is " << sum << endl;
}
}
return 0;
}
|
Вопрос в том, стоит ли искать последний элемент в отдельном цикле начиная с конца массива? Сильно ли мы экономим на количестве операций. Будет этот алгоритм эффективнее или нет? | |
|
|
|
|
автор: КОдер (03.06.2014 в 23:38) |
|
|
для: agon
(31.08.2009 в 16:06)
| | КАл полный | |
|
|
|
|