VPF::массив, сортировка - Форум программистов

Артем125

Дата 12.10.2009, 21:32 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

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

Здравствуйте,

есть массив, достается из базы. целые числа.
допустим у нас есть ряд 0,1,3,6. Необходимо найти минимальное значение в свободном промежутке. найти 2
в следующем ряду 1,2 найти 3
в этом 4,5,6 найти 3
и т.д. Может есть стандартная функция по поиску свободного значения в интервале значений массива

Цель: допустим есть ряд от 1 до 10 без промежутков. в произвольном порядке удаляются цифры. Так вот чтобы не продолжать ряд.. 11,12..99..n

Моя функция не фурычит

Код


function pagesOrder()
{
    $query = "SELECT pages_order FROM ".TABLE_PAGES." WHERE page_parent = '".PAGE_PARENT_FIRST."'";
    $result = mysql_query($query);
    if (!$result) {
        $msg = 'Ошибка';
        $err = 'Ошибка при выполнении запроса: <br/>'.
             $query.'<br/>'.mysql_errno().':&nbsp;'.mysql_error().'<br/>'.
             '(Файл '. __FILE__ .', строка '. __LINE__ .')';
        return showErrorMessage( $msg, $err, true, '' );
    }    
    if(mysql_num_rows($result) > 0)
    {    
        $m = array();
        while ($row = mysql_fetch_assoc($result))
        {
            $m[] = $row['pages_order'];
        }    
        sort($m);
        
        for ($i = 0; $i < (count($m)+1); $i++)
        {    
            if (isset($m[$i+1]) && isset($m[$i]))
            {     
                if (($m[$i+1] - $m[$i]) > 2)
                {
                    return intval($m[$i] + 1);
                }
                
            }
        }
        
    }
    else 
    {
        return 1;
    }
        
return FALSE;
}

Это сообщение отредактировал(а) Артем125 - 12.10.2009, 21:47

brother79

Дата 13.10.2009, 17:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 2
Всего: 6

Я могу только словами описать алгоритм как сам делал такую задачу двоичным поиском.

вычисляешь кол-во эл-ов. Если оно меньш чем разница между последним и первым - то есть дырка. Берёшь середину, и также смотришь разницу также только для 2-х половинок массива, если дырка в первом, то делишь первый, если во втором - то второй, и т.д., пока массив до 3-х или 2-х не уменьшится.

--------------------

http://www.nastandart.com

NLspieler

Дата 13.10.2009, 17:53 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 16
Всего: 19

не понял вашу задачу.
Но кажется необходимые стандартные функции существуют

Артем125

Дата 13.10.2009, 19:04 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

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

Цитата(brother79 @ 13.10.2009, 17:16)

задача двоичным поиском.

Спасибо, я тоже пришел к такому аглоритму )))) пока правда не реализовал, извернулся по другому

Добавлено @ 19:09

Цитата(NLspieler @ 13.10.2009, 17:53)

не понял вашу задачу.
Но кажется необходимые стандартные функции существуют

к сожалению такой функции не нашел, а перерыл я много

есть к примеру ряд 1,4,5,8,16, он может быть любого количества элементов и лбого диапазона... переодически элементы заменяются, удаляются, добавляются....
задача вставлять в него элементы значения дмапозона в данном случае от 1 до 16, если дырки нет, то 17, если нет ни одного элемента то 0

заполняется в сделующем порядке. нет элементо... ввод 0 значение, есть 0 значение, ввод 1 значение, есть 01 ввод 2, есть 012 ввод 3 и т.д. а помтом при уделении например элемента со значением 1 получаем ряд 02. При удалении 2, получаем 0..

Это сообщение отредактировал(а) Артем125 - 13.10.2009, 19:21

brother79

Дата 13.10.2009, 19:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 2
Всего: 6

Кстати в каком-то языке связанным с вебом такая ф-я была, только когда она мне попадалась - оно мне не надо было, а счас не вспомню, проще самому написать.

--------------------

http://www.nastandart.com

Артем125

Дата 13.10.2009, 19:23 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

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

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

Кстати, когда почитывал Подбельскую, учебник С++, там много описаний функций стандартной библиотеки... и количество функций там впечатляет как и количество библиотек, а тут блин, по десятку функций всего для работы различными сушностями ((

Это сообщение отредактировал(а) Артем125 - 13.10.2009, 19:27

brother79

Дата 14.10.2009, 13:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 2
Всего: 6

Код


//---------------------------------------------------------------------------
// Найти код свободный
  bool Kod_In(TDataSet *Q, TSString Field, int a, int b)
  {
    int aa, bb;
    if (Q == NULL) return false;
    Q->RecNo = a;
    aa = Q->FieldByName(Field.c_str())->AsInteger;
    Q->RecNo = b;
    bb = Q->FieldByName(Field.c_str())->AsInteger;
    return (bb-aa > b-a);
  }
//---------------------------------------------------------------------------
int TSprTableInfo::getKod(TComponent *AOwner, TSString Field, TSString Usl)
{
  if (Field.IsEmpty())
    return -1;
  TDataSet *Q = NULL;
  int Result;
  if (GET_BIT(Options, SPR_TABLE_AUTO_INC)) { // это выкинь
    Q = dataBase->execSQLSelect(AOwner, this, "SELECT " + Field + " FROM " + name + " " + name + "0" + Usl + " ORDER by " + Field+" desc");
    if (Q == NULL)
      return 1;
    Q->First();
    Result = Q->FieldByName(Field.c_str())->AsInteger + 1;
    dataBase->queryFree(&Q);
    return Result;
  } else {
    int a, b, c;
    if (!Usl.IsEmpty())
      Usl = " WHERE " + Usl;
    Q = dataBase->execSQLSelect(AOwner, this, "SELECT " + Field + " FROM " + name + " " + name + "0" + Usl + " ORDER by " + Field);
    if (Q == NULL)
      return 1;
    a = 1;
    b = Q->RecordCount;
    Q->First();
    if (Q->FieldByName(Field.c_str())->AsInteger > 1) //тут проверка если диапозон не с 1, но сразу 1
      Result = 1;
    else
    {
      if (Kod_In(Q, Field, a, b)) // тут проверка может и вовсе дырок нету
      {
        while (Kod_In(Q, Field, a, b) && (b-a > 1)) // тут банальный двоичный поиск
        {
          c = (a + b) / 2;
          if (Kod_In(Q, Field, a, c)) b = c;
                              else a = c;
        }
        Q->RecNo = a;
      } else
      {
        Q->Last();
      }
      Result = Q->FieldByName(Field.c_str())->AsInteger + 1;
    }
  }
  dataBase->queryFree(&Q);
  return Result;
}

Если ентересно, есть прекрасно работающий код, правда не php и не с массивом, но

aa = Q->FieldByName(Field.c_str())->AsInteger;

заменить на $aa = $array[$Field]; - думаю не сложно будет. Просто это писалось очень давно, ещё для парадоксовых баз, и никогда не переделывалось, и сейчас мне перекладывать на php смысла нету, а тебе если не хочется отлаживать - можешь переложить на php

Это сообщение отредактировал(а) brother79 - 14.10.2009, 13:59

--------------------

http://www.nastandart.com

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Общие вопросы \| Следующая тема »