поиск в массиве

[zip]

Дан массив случайных чисел в диапазоне от -20 до +20. Как найти позиции крайних отрицательных элементов (самого левого отрицательного элемента и самого правого отрицательного элемента)?

Сообщение отредактировано: zip - 05.02.04, 18:27

[rusty_angel]

Просматриваешь массив. Индекс первого отрицательного числа, которое встретится, и есть "позиция самого левого отрицательного элемента". А чтобы найти самый правый, просматривай массив с конца

[Flex Ferrum]

// Поиск первого отрицательного элемента
std::vector<int>::iterator first_negate = std::find_if(arr.begin(), arr.end(), std::bind2nd(std::less<int>(), 0));
// Поиск последнего отрцательного элемента
std::vector<int>::reverse_iterator last_negate = std::find_if(arr.rbegin(), arr.rend(), std::bind2nd(std::less<int>(), 0));

[Sazabis]

Заполнять массив я думаю понятно как, тогда fn_idx - индекс первого, ln_idx - последнего

void func( int *mass, int count, int &fn_idx, int &ln_idx ){
  for( int i=0;i<count;i++ ){
    if( mass[ i ] < 0 )ln_idx = ( fn_idx == -1 ) ? (fn_idx = i) : i;
  }
}

[Flex Ferrum]

На самом деле - не совсем оптимально. При любом раскладе нужно перебрать все элементы массива. В таком варианте:

 
void func(int* mas, int count, int& first, int& last)
{
   int n;
   first = last = -1;
   for (n = 0; n < count && first == -1; first = mas[n] < 0 ? n : -1, ++ n);
   if (first == -1)
      return;
 
   for (n = count - 1; n >= first && last == -1; last = mas[n] < 0 ? n : -1; ++ n);
}

Таким образом получается, что все элементы массива будут проверены только в худшем случае.

[Sazabis]

согласен
только last=first=-1 зачем ? разве функция должна заботится о верности допустим count ?, аналогично и для last first.

[Flex Ferrum]

Цитата

Sazabis, 6.02.04, 11:47
только last=first=-1 зачем ? разве функция должна заботится о верности допустим count ?, аналогично и для last first.

Предлагаемый интерфейс предполагает, что в случае неприсутствия отрицательных элементов в массиве возвращается -1. Эта строчка и обеспечивает это условия. Тогда пользоваться этим методом можно так:

 
int first, last;
func(mas, count, first, last);

В твоем варианте необходимо:

 
int first = -1, last = -1;
func(mas, count, first, last);

Зачем заставлять пользователя писать лишний код?

[Sazabis]

но тогда, если first, допустим известен ( 10 ), ты будешь искать его заного

[Flex Ferrum]

Цитата

Sazabis, 6.02.04, 12:04
но тогда, если first, допустим известен ( 10 ), ты будешь искать его заного

Ну а если он просто напросто не проинициализирован?

[Sazabis]

Цитата

Flex_Ferrum, 6.02.04, 12:07
Ну а если он просто напросто не проинициализирован?

значит он останется таким

функция свою задачу выполнела ? если не -1 то искать...

Сообщение отредактировано: Sazabis - 06.02.04, 09:14

[Flex Ferrum]

Цитата

Sazabis, 6.02.04, 12:13
значит он останется таким

Что есть не хорошо.

[zip]

Я написал эту программу, может кому будет интересно. Вот полное условие:

Дан массив случайных чисел в диапазоне от -20 до +20. Необходимо найти позиции крайних отрицательных элементов (самого левого отрицательного элемента и самого правого отрицательного элемента) и отсортировать элементы, находящиеся между ними

А вот программа:

 
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
 
int firstlast(int array[])
{
    int first,last;
    for (int i=0;i<10;i++)
    {
        if (array[i]<0)
        {
            first=i+1;
            break;
        }
    }
 
    for (int j=9;j>=0;j--)
    {
        if (array[j]<0)
        {
            last=j+1;
            break;
        }
    }
    cout<<"sortirovka mejdu chislami: "<<array[first-1]<<" and "<<array[last-1]<<endl;
    int mejdu=last-first-1;
    int temp;
    for (int a=first;a<last-2;a++)
    {
        for (int c=a+1;c<last-1;c++)
        {
            if (array[c]<array[a])
            {
                temp=array[a];
                array[a]=array[c];
                array[c]=temp;
            }
        }
    }
    for (a=0;a<10;a++)
        cout<<array[a]<<" ";
    cout<<endl;
 
    return 0;
}
 
 
void main()
{
    srand(time(NULL));
    int array[10];
    cout<<"massiv:\n";
    for (int i=0;i<10;i++)
    {
        array[i]=(rand()%41)-20;
        cout<<array[i]<<" ";
    }
    cout<<endl;
    firstlast(array);
}

[Flex Ferrum]

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

[Sazabis]

молодец, решил свою задачу своим способом. И тут таки вездесущий Flex_Ferrum, оказался прав

Цитата

Flex_Ferrum, 6.02.04, 12:07
Ну а если он просто напросто не проинициализирован?