Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Задачка с собеседования (с/с++), поиск в массиве  
V
    Опции темы
vitlic
Дата 2.4.2007, 14:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 74
Регистрация: 22.2.2007
Где: где home(){return где="тут"}

Репутация: 1
Всего: 1
Был на собеседование в одной фирме на должность с/с++ embeded  программиста. Задали вопрос, который на мой взгляд решил оптимально. 
Может кто-нибудь знает как решить более оптимально?

Задача: есть int массив n чисел. Нужно проверить есть ли в нем число k.

Обычное решение:

Код

int i=0;

while(i<n && arr[i]!=k) i++;

if(a[i]==k) return i;
return -1;

 

При таком подходе в худшем случае,  когда "к" не находиться в масиве, делается 2n+2 проверок (сравнений)

Мое решение:
Код

int i=0;

if(a[n-1]==k) return n-1;
else
{
      a[n-1]=k;
      while(a[i]!=k) i++;      
}

i--;
if(i!=n-1) return i;
else return -1;


Сейчас в худшем случае делается n+2 проверок (сравнений).

Есть ли еще какие-нибудь оптимизации? 
PM WWW   Вверх
Sartorius
Дата 2.4.2007, 14:37 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
 Не по теме немного ))
 А что же вернется в первом случае, если i == n?
 Во втором случае нашли мы a[i] == k, а потом i-- делаем. ...

 PS а используя ограничивающий элемент в конце массива , оптимизировать больше некуда, если конечно никаких других данных о массиве у нас нет ))) ясно, что меньше чем n сравнениями не обойтись smile 

Это сообщение отредактировал(а) Sartorius - 2.4.2007, 14:42
PM MAIL ICQ   Вверх
Xenon
Дата 2.4.2007, 14:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1529
Регистрация: 12.4.2006

Репутация: 11
Всего: 50
Думал-думал и пока ничего лучше не придумал smile
... Удалил smile

Это сообщение отредактировал(а) Xenon - 2.4.2007, 14:59


--------------------
user posted image  
PM MAIL   Вверх
Fazil6
Дата 2.4.2007, 14:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1653
Регистрация: 3.5.2006
Где: Минск

Репутация: 35
Всего: 60
Код

int find(int a[], int n, int k)
{
    if(!n) return -1; 
    while(a[--n]!=k && n) ;
    return a[n]==k ? n :  -1 ;
}


Это сообщение отредактировал(а) Fazil6 - 2.4.2007, 14:55
PM MAIL   Вверх
Sartorius
Дата 2.4.2007, 14:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
удалил...

Это сообщение отредактировал(а) Sartorius - 2.4.2007, 14:54
PM MAIL ICQ   Вверх
vitlic
Дата 2.4.2007, 15:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 74
Регистрация: 22.2.2007
Где: где home(){return где="тут"}

Репутация: 1
Всего: 1
Цитата(Sartorius @ 2.4.2007,  14:37)
Не по теме немного ))
 А что же вернется в первом случае, если i == n?
 Во втором случае нашли мы a[i] == k, а потом i-- делаем. ...

 PS а используя ограничивающий элемент в конце массива , оптимизировать больше некуда, если конечно никаких других данных о массиве у нас нет ))) ясно, что меньше чем n сравнениями не обойтись smile

про i==n забыл, писал на скорую руку)
насчет i-- ты прав smile

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

Добавлено через 1 минуту и 54 секунды
Цитата(Fazil6 @ 2.4.2007,  14:50)
Код

int find(int a[], int n, int k)
{
    if(!n) return -1; 
    while(a[--n]!=k && n) ;
    return a[n]==k ? n :  -1 ;
}

Решение с эстетической точки зрения красивое, но здесь 2n сравнений..
PM WWW   Вверх
HappyLife
Дата 2.4.2007, 17:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 642
Регистрация: 17.5.2006

Репутация: 3
Всего: 8
Цитата(vitlic @ 2.4.2007,  14:27)
Мое решение:
Код

int i=0;

if(a[n-1]==k) return n-1;
else
{
      a[n-1]=k;
      while(a[i]!=k) i++;      
}

i--;
if(i!=n-1) return i;
else return -1;


Сейчас в худшем случае делается n+2 проверок (сравнений).

Есть ли еще какие-нибудь оптимизации?

Не соглашусь совершенно. Делаеться 2n + 2 сравнений.

1n. a[i]!=k
2n в условии while проверка на нуль...
PM MAIL   Вверх
Sartorius
Дата 2.4.2007, 17:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
HappyLife, 

Цитата

2n в условии while проверка на нуль...


 где??? 
PM MAIL ICQ   Вверх
HappyLife
Дата 2.4.2007, 17:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 642
Регистрация: 17.5.2006

Репутация: 3
Всего: 8


Добавлено @ 17:21
Sartorius, 
While сам по себе обладает такой конструкцией, что чтобы выйти из цикла сверяет булевое выражение....

Это сообщение отредактировал(а) HappyLife - 2.4.2007, 17:23
PM MAIL   Вверх
Daevaorn
Дата 2.4.2007, 17:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: 51
Всего: 70
Цитата(HappyLife @  2.4.2007,  18:16 Найти цитируемый пост)
 условии while проверка на нуль...

да, и вправду, где? Там проверка a[i]!=k на истинность.
PM MAIL WWW   Вверх
threef
Дата 2.4.2007, 17:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 375
Регистрация: 27.10.2005
Где: Запорожье

Репутация: 9
Всего: 10
vitlic, 
ты запортил элемент массива - обидел работодателей.
Код

if( *a == k)
   return 0;
else
{
     Type * i=a+n-1,tmp=*a;
     *a=k;
      while( *i-- != k);  // для целых вместо != можно ^
      *a=tmp; //безусловно
      return i-a? i-a:-1; // если i==a то i-a == 0=>false
}      
PM MAIL   Вверх
Sartorius
Дата 2.4.2007, 17:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
HappyLife, я думаю современные компиляторы все таки умеют оптимизировать обработку простых логических выражений.... 
PM MAIL ICQ   Вверх
HappyLife
Дата 2.4.2007, 17:29 (ссылка) | (голосов:3) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 642
Регистрация: 17.5.2006

Репутация: 3
Всего: 8
Я бы сделал так.
Код

int myfind(int a[],int n,int k)
{
try{
    while(a[--n]^k);
    return n;
}catch(...)
{
    return -1;
}
}


Это сообщение отредактировал(а) HappyLife - 2.4.2007, 17:32
PM MAIL   Вверх
Sartorius
Дата 2.4.2007, 17:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
HappyLife,  а теперь представь, что вставит компилятор для проверки границ и выброса исключения.(Если оно вообще будет)

Это сообщение отредактировал(а) Sartorius - 2.4.2007, 17:32
PM MAIL ICQ   Вверх
threef
Дата 2.4.2007, 17:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 375
Регистрация: 27.10.2005
Где: Запорожье

Репутация: 9
Всего: 10
а корифеи  не рекомендуют использовать исключения в виде составляющей алгоритмов. 
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0573 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.