Страница 1 из 3

Требуется програмист со знанием алгоритмов

Добавлено: 26 ноя 2010, 15:22
unknown
Я придумал программу, но не могу составить к ней алгоритм поэтому ищу человека который мог бы это сделать.
Нужная программа очень экономит время для тех кто опаздывает куда нибудь)

подробнее здесь:Irc.lan.du канал school№8 ник Unknown

Re: Требуется програмист со знанием алгоритмов

Добавлено: 26 ноя 2010, 23:58
DOKA
По ссылке:

Код: Выделить всё

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

Код: Выделить всё

Аватар: нет мозга

Опишите здесь, что за алгоритм, требуемый язык исполнения, сроки и бюджет проекта.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 27 ноя 2010, 00:34
Filimon Кykyev
Дока, кто ж по таким сцылкам ходит и смысл жизни ищет, у тебя что "нет мозга"? :wink: :smile:

Re: Требуется програмист со знанием алгоритмов

Добавлено: 27 ноя 2010, 11:19
unknown
и так, Бюджет это общественные начала, я не могу оценить проект.

язык м не помню, но вобщем обычное окно не помню как называется, можете писать в мирку #school№8
ник Unknown

Re: Требуется програмист со знанием алгоритмов

Добавлено: 28 сен 2011, 01:47
pashan
ну, что, составили алгоритм? теперь можно грабить корованы? :ROFL:

Re: Требуется програмист со знанием алгоритмов

Добавлено: 28 сен 2011, 02:01
Basileos
Сегодня что, день археолога?

Re: Требуется програмист со знанием алгоритмов

Добавлено: 29 сен 2011, 16:01
pashan
Basileos писал(а):Сегодня что, день археолога?
не ну фигле, ветка ж мёртвая. надо пнуть.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 15:27
Volochinuk
Basileos писал(а):Сегодня что, день археолога?
Так хотя бы само ТЗ к алгоритму выложил, так поупражняться на досуге. Жадина прямо:). Может тут бы его и соорудили бы:).

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 15:38
LuckyOne [away]
Держи простенькую задачку на поупражняться, для любого строго типизированного языка типа плюсов или джавы.

Дан массив в N (10,100,1000...N) элементов фиксированного типа INT (знаковый - как положительные, так и отрицательные), в котором могут встретиться элементы, близкие по модулю к INT_MAX, но общей суммой гарантированно меньше INT_MAX. Сложи все элементы данного массива, используя исключительно промежуточные переменные того же типа INT (т.е. никаких более размерных типов). Ответ надо отдать тоже типом INT.

зы: естественно, для получения правильного ответа нужно избежать переполнения типа при сложении.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 17:43
Ism
Тогда надо запретить использование любого типа алгоритмов сортировки=)

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 17:46
Ega23
Я тут с температурой и сильно думать не получается.
Но вроде как решается без всяких сортировок и в один проход по массиву. Ну и две переменные, одна под результат, другая - своего рода стек разрядов.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 17:48
Ega23
И N должно быть меньше MAX_INT. :)

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 20:10
LuckyOne [away]
Ism писал(а):Тогда надо запретить использование любого типа алгоритмов сортировки=)
хорошо, пусть первым будет отсортированный массив вида: [ -INT_MAX + 1, -INT_MAX + 2, 0, +INT_MAX - 2, +INT_MAX - 1]. Алгоритм кое-где всё равно нужен, да? :)
Ega23 писал(а):Я тут с температурой и сильно думать не получается.
Но вроде как решается без всяких сортировок и в один проход по массиву. Ну и две переменные, одна под результат, другая - своего рода стек разрядов.
Итить! Не подсказывать, пусть человек сам домучает алгоритм. И проверку на переполнение без эксепшнов и переполнений соорудит.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 20:27
Ega23
Век живи - век учись. В процессе написания теста выяснил одну любопытную фишку. Сижу и гуглю, так ли это.

UPD. В натуре туплю из-за температуры. Вспомнил, что уже с таким сталкивался.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 21:23
SaaBaka
Тоже мне, бином Ньютона. Обычное сложение с переносом (hw - для хранения переноса, lw - младшая часть):

Код: Выделить всё

void add(int& hw, int& lw, int x)
{
    int sum = lw + x;
    lw = (sum & (INT_MAX+1U)) ? (((x > 0) ? ++hw : --hw), sum & INT_MAX) : sum; 
}
// использовать так:
int hw(0), lw(0);
for (int i = 0; i < array_size; ++i)
   add(hw, lw, array[i]);
// результат будет в lw; для общего случая резуьтат = lw + hw*(INT_MAX+1U)
Кстати, этот как раз тот случай, когда на ассемблере такое сложение - ровно две машинные инструкции (add+adc), а на языке более высокого уровня надо огород городить.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 22:38
LuckyOne [away]
SaaBaka писал(а):Кстати, этот как раз тот случай, когда на ассемблере такое сложение - ровно две машинные инструкции (add+adc), а на языке более высокого уровня надо огород городить.
Ну почти есть решение! Вот только представим, что у нас не ассемблер конкретного процессора, и мы не знаем, что получится в результате lw + x или INT_MAX+1U. Implementation defined. overflow_error. Да мало ли еще какая бяка.. Короче, надо бы это как-то обойти, да? Языки высокого уровня компилируются на разных процессорах, и нам нужно, чтобы результат был предсказуем.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 22:45
Ega23
LuckyOne [away] писал(а):INT_MAX+1U. Implementation defined. overflow_error.
Тоже смутило.
INT_MIN использовать можно? А то уж больно геморно старший бит выставлять, бо размер INT заранее не указан.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 22:56
SaaBaka
LuckyOne [away] писал(а):Ну почти есть решение! Вот только представим, что у нас не ассемблер конкретного процессора, и мы не знаем, что получится в результате lw + x или INT_MAX+1U.
На всех известных мне процессорах (x86, x64, ARM, MIPS, SPARC, IA64, плюс всякие микроконтроллеры) получится именно это - старший бит в целых используется для знака, не зависимо от длины слова. И не будет никаких overflow.

Можете привести обратный пример :D

Ну а если вы такие занудные и не хотите работать с битами, вместо проверки старшего бита можно использовать условие sum < x.

И я еще застал девайсы вроде i8048, где вообще не было инструкции SUB :)

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 23:11
Ega23
SaaBaka писал(а):старший бит в целых используется для знака, не зависимо от длины слова. И не будет никаких overflow.
Если по-хрестоматийному, то надо INT_MAX привести к беззнаковому, прибавить единицу, и после этого привести к знаковому.
Хотя чё-й та я торможу. INT_MIN = not INT_MAX.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 23:16
SaaBaka
Запись INT_MAX+1U именно это и означает. Буква U там не просто так :) А вообще INT_MAX = ((1 << (INT_BITS - 1) - 1), если INT_BITS - ширина целого значения в битах.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 23:22
Ega23
SaaBaka писал(а):Запись INT_MAX+1U именно это и означает.
Я понимаю. Я не настолько хорошо владею сями, чтобы сходу такие весчи читать, но гугл ещё никто не отменял.
Но изначально в условии говорилось о языке со строгой типизацией.
В том же пацкале запись

const
c = 1;

даст разный результат в разных версиях компилятора.
Точнее, sizeof(c) даст разный результат.

А приведение этой пихни к Variant вообще чудеса даёт.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 23:29
SaaBaka
Ну так мой вариант работает при любой ширине слова. Хоть char туда подставь (и заменив INT_MAX на SCHAR_MAX). Можно вообще эти ...MAX не использовать, а вместо него (1 << (sizeof(n)*8 - 1) - 1), где n может быть целым любого типа/любой длины. Просто лаки хотел INT_MAX, а мне не жалко :)

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 23:32
LuckyOne [away]
Устал сегодня, лень писать самому. Отделаюсь копипастой :)

Код: Выделить всё

int add(int lhs, int rhs) {
 if (lhs >= 0 && rhs >= 0) {
  if ( ( INT_MAX - lhs ) <= rhs) {
   /* overflow has occurred */
  }
 }
 else if (lhs < 0 && rhs < 0) {
  if (lhs <= ( INT_MIN - rhs ) ) {
   /* overflow has occurred */
  }
 }
}
Никаких MAX+1, исключительно вычитания и больше-меньше. Причем кроссплатформенные :)

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 23:36
Ega23
Я так понимаю, что Лаки хотел сравнений (INT_MAX - x).
Хотя я уже всё, не соображаю совсем, 39,2.

Re: Требуется програмист со знанием алгоритмов

Добавлено: 11 ноя 2014, 23:39
SaaBaka
Мой вариант короче, проще и быстрее :) И в общем-то не менее кроссплатформенный, для всех практических применений.
:oops: