Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Нужно написать функцию которая возвращает индекс

Автор: vovamakr 2.11.2015, 22:05

Нужно написать функцию которая возвращает индекс элемента в массиве который мы ищем. Массив наполнять вручную.. Если такого значения нет , повернуть размер массива. Массив отсортирован. Я без понятия как делать. Помогите написать.

Автор: feodorv 2.11.2015, 22:15

Цитата(vovamakr @ 2.11.2015, 22:05

)

Массив отсортирован

https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA?

Цитата(vovamakr @ 2.11.2015, 22:05

)

повернуть размер массива

Что сделать?

Автор: vovamakr 3.11.2015, 10:39

feodorv, хз, препод сказа цыклом пройтись и найти индекс
повернуть что то чтобы не перепутать с индексом

Автор: feodorv 3.11.2015, 10:49

Цитата(vovamakr @ 3.11.2015, 10:39

)

повернуть что то чтобы не перепутать с индексом

Может, всё-таки вернуть из функции? Вам абсолютно всё равно, что и как, лишь бы сдать? Тогда Вам в "http://forum.vingrad.ru/forum/Vingrad-help-center.html". По ссылке, что я Вам дал, можно найти код на C и C++, нужно будет только изменить возвращаемое из функции значение.

Автор: vovamakr 3.11.2015, 11:00

feodorv, я там не нашел ничего про массив(

Автор: feodorv 3.11.2015, 11:26

Цитата(vovamakr @ 3.11.2015, 11:00

)

feodorv, я там не нашел ничего про массив(

По ссылке? Не нашли???

Цитата

Пример кода на языке программирования Си для поиска элемента x в массиве a[n], отсортированного в возрастающем порядке:

А в "Центр помощи" скопируйте своё первое сообщение. Не забудьте указать в заголовке в квадратных скобках язык программирования.

Автор: vovamakr 3.11.2015, 11:48

сделал:

Код


int Array(int* array, int value, int size)
{
 
    
    for (int index = 0; index < size; ++index)
    {
        if (array[index] == value)
            return index;
        else
            return size;
    }
}
int main()
{
    int array[10] = { 1, 3, 5, 7, 8 };
 
    int pr = Array(array, 5, 10);
    printf("Value index:%d\n", pr);
 
}

Автор: feodorv 3.11.2015, 11:50

Код


#include <stdio.h>

unsigned int binarySearch( int m[], unsigned int size, int value)
{
    unsigned int first = 0;
    unsigned last = size;

    while( first < last ) 
    {
        unsigned int mid = (first + last) / 2;

        if( value == m[mid] ) return mid;

        if( value < m[mid] )
            last = mid;
        else
            first = mid + 1;
    }

    return size;
}

int main()
{
    int mass[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
    unsigned int index = binarySearch( mass, 10, 13);
    if( index < 10 )
      printf( "Found, index = %u\n", index);
    else
      printf( "Not found\n" );
    return 0;
}

Цитата(vovamakr @ 3.11.2015, 11:48

)

сделал

А если:

Цитата(vovamakr @ 3.11.2015, 11:48

)

int pr = Array(array, 5, 3);

Автор: vovamakr 3.11.2015, 12:02

Код


#include <cstdio>

int Array(int* array, int value)
{
    int size = (sizeof (array)) / sizeof(array[0]);
    for (int index = 0; index < size; ++index)
    {
        if (array[index] == value)
            return index;
    }
    return size;
}
int main()
{
    int array[10] = { 1, 3, 5, 7, 8 };

    int pr = Array(array, 3);
    printf("Value index:%d\n", pr);

}

Автор: math64 3.11.2015, 12:09

Цитата(vovamakr @ 3.11.2015, 12:02

)

Код


int size = (sizeof (array)) / sizeof(array[0]);

Так можно писать когда array объявлен как массив (в main).
В Array он передается как указатель. Поэтому size получится равным 1 (на 32-разрядной ОС)

Автор: vovamakr 3.11.2015, 12:20

math64, а как сделать чтобы норм работало?

Автор: rudolfninja 3.11.2015, 12:57

Цитата(vovamakr @ 3.11.2015, 12:20

)

а как сделать чтобы норм работало?

Передавать в функцию размер массива. Это вполне нормальная и распространенная практика.

Автор: feodorv 3.11.2015, 12:57

Цитата(vovamakr @ 3.11.2015, 12:20

)

а как сделать чтобы норм работало?

Передавать размер массива дополнительным аргументом функции:

Цитата(vovamakr @ 3.11.2015, 12:02

)

int Array(int* array, int size, int value)

Ну, и осталось учесть, что

Цитата(vovamakr @ 2.11.2015, 22:05

)

Массив отсортирован

Автор: rudolfninja 3.11.2015, 13:04

Я думаю, что раз ему сказали в цЫкле smile

пробежать по массиву и найти индекс, то факт, что массив отсортирован - бесполезный. Да и не думаю, что автор сам сможет бинарный поиск реализовать.

Автор: vovamakr 3.11.2015, 13:05

feodorv,

Код


#include <cstdio>

 int FindValueInArray(const int* array, int value, int size)
{


    for (int index = 0; index < array[value]; ++index) // бинарный поиск я спрашывал в  препода следущее задание. А  тут  нужно пройтись покы етот елемент  больше следущих  
    {
        if (array[index] == value)
            return index;
    }
    return size;
}
int main()
{
    int array[5] = { 1, 3, 5, 7, 8 };

    int pr = FindValueInArray(array, 8, 5);
    printf("Value index:%d\n", pr);

}

Автор: rudolfninja 3.11.2015, 13:12

Цитата(vovamakr @ 3.11.2015, 13:05

)

(int index = 0; index < array[value]; ++index)

Что-то тут не так.
Допустим, у нас массив 10, 20, 30, 40. Как видно массив состоит из 4 элементов. Мы хотим найти индекс элемента со значением 30.
Как думаете, что будет в случае array[30]? Будет совсем не то, что вы планируете.

Автор: vovamakr 3.11.2015, 13:14

rudolfninja, А как написать? Я только учу и не знаю как правильно(
будет array[30] а у нас arra[4]

Автор: rudolfninja 3.11.2015, 13:18

Цитата(vovamakr @ 3.11.2015, 13:05

)

int FindValueInArray(const int* array, int value, int size)
{
    for (int index = 0; index < array[value]; ++index) // бинарный поиск я спрашывал в  препода следущее задание. А  тут  нужно пройтись покы етот елемент  больше следущих
    {
        if (array[index] == value)
            return index;
    }
    return size;
}

Смотрите, зачем в эту функцию, по-вашему, передается размер массива? - Не только для того, чтоб вернуть его в случае, когда в массиве нет искомого элемента, но и для того, чтобы знать, когда заканчивать цикл обработки массива.

Автор: vovamakr 3.11.2015, 13:23

rudolfninja, )) посмотрите мои посты ранее. но мне нужно чтобы не доходил цикл до конца а до индекса значения value

Автор: rudolfninja 3.11.2015, 13:25

Цитата(vovamakr @ 3.11.2015, 13:23

)

но мне нужно чтобы не доходил цикл до конца а до индекса значения value

А как быть, если этого значения нет в массиве?
Не говорите, что вернуть размер массива =) Я имею в виду, как ваша программа узнает это?

Автор: vovamakr 3.11.2015, 13:28

Цитата(rudolfninja @ 3.11.2015, 13:25

)

как быть, если этого значения нет в массиве?
Не говорите, что вернуть размер массива =) Я имею в виду, как ваша программа узнает это?

я об этом не подумал.... но зачем препод дал такое. только не говорите чтобы мены проверить. я только 2 месяца учусь (1 курс)

Автор: rudolfninja 3.11.2015, 13:34

Что то я не могу придумать как в данном случае использовать то, что массив отсортирован. Единственный вариант, который приходит на ум, это то, что написал federov, то есть использование бинарного поиска.
Даже если массив отсортирован, то мы, не зная его размер, можем с легкостью выйти за пределы массива.

Автор: feodorv 3.11.2015, 13:40

Было же так:

Цитата(vovamakr @ 3.11.2015, 12:02

)

for (int index = 0; index < size; ++index)

А вообще, можно же прекратить ползать по массиву, если искомое значение стало меньше значения в массиве:

Код


int FindValueInArray(const int* array, int value, int size)
{
    for (int index = 0; index < size && value >= array[index]; ++index)
    {
        if (array[index] == value) return index;
    }
    return size;
}

Автор: rudolfninja 3.11.2015, 13:43

Цитата(feodorv @ 3.11.2015, 13:40

)

можно же прекратить ползать по массиву, если искомое значение стало меньше значения в массиве:

Но если искомого значения нет в массиве и оно больше максимального элемнта (например, в массиве 1 2 3 4 5 ищем 10), то цикл будет бесконечный.

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

Автор: feodorv 3.11.2015, 13:49

Цитата(rudolfninja @ 3.11.2015, 13:43

)

то цикл будет бесконечный

Почему?

Цитата(feodorv @ 3.11.2015, 13:40

)

index < size && value >= array[index]

Автор: rudolfninja 3.11.2015, 13:52

feodorv, совершенно верно! =) Я исправлся в прошлом сообщении. Имел в виду, что не используя размер массива может произойти такая ситуация.
vovamakr, я предлагаю вам использовать вариант, который предложил feodorv. По-моему, он наиболее подходящий в вашем случае.

Автор: feodorv 3.11.2015, 14:11

Цитата(rudolfninja @ 3.11.2015, 13:52

)

Имел в виду, что не используя размер массива может произойти такая ситуация.

Нет, нет, без размера никак)))

Автор: math64 3.11.2015, 15:07

Цитата(feodorv @ 3.11.2015, 14:11

)

Нет, нет, без размера никак)))

Можно в конец массива одавить ещё один элемент 0x7FFFFFFF, явлаяющийся признаков конца массива (как '\0' для строк). Но при этом в массиве значение 0x7FFFFFFF будет запрещено.

Автор: feodorv 3.11.2015, 15:23

Цитата(math64 @ 3.11.2015, 15:07

)

Можно в конец массива одавить ещё один элемент 0x7FFFFFFF

Можно))) Но возвращать-то в случае быстрого выхода из цикла по условию value < array[index] всё равно размер массива, что заставляет нас продолжать просматривать массив до конца, что делает применение этого условия бесполезным (да и отсортированность массива тоже))))

Автор: vovamakr 3.11.2015, 18:04

Цитата(feodorv @ 3.11.2015, 11:50

)

unsigned int mid = (first + last) / 2;
if( value == m[mid] ) return mid;

у Вас в коде mid что это?

Автор: feodorv 3.11.2015, 18:13

Цитата(vovamakr @ 3.11.2015, 18:04

)

у Вас в коде mid что это?

Индекс элемента, лежащего ровно посередине между first и last.

Автор: goodluck 10.11.2015, 14:32

Модератор: Сообщение скрыто.