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

Сообщение
Автор
unknown
Сообщения: 2
Зарегистрирован: 08 ноя 2010, 16:48

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

#1 Сообщение unknown » 26 ноя 2010, 15:22

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

подробнее здесь:Irc.lan.du канал school№8 ник Unknown
Последний раз редактировалось unknown 27 ноя 2010, 18:06, всего редактировалось 1 раз.

DOKA
Сообщения: 5738
Зарегистрирован: 25 дек 2007, 21:27

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

#2 Сообщение DOKA » 26 ноя 2010, 23:58

По ссылке:

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

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

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

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

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

Аватара пользователя
Filimon Кykyev
Сообщения: 15458
Зарегистрирован: 18 апр 2008, 22:15
Откуда: БВ-ЛБ
Контактная информация:

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

#3 Сообщение Filimon Кykyev » 27 ноя 2010, 00:34

Дока, кто ж по таким сцылкам ходит и смысл жизни ищет, у тебя что "нет мозга"? :wink: :smile:

unknown
Сообщения: 2
Зарегистрирован: 08 ноя 2010, 16:48

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

#4 Сообщение unknown » 27 ноя 2010, 11:19

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

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

Аватара пользователя
pashan
Сообщения: 1606
Зарегистрирован: 09 янв 2008, 13:56

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

#5 Сообщение pashan » 28 сен 2011, 01:47

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

Аватара пользователя
Basileos
Сообщения: 3587
Зарегистрирован: 25 авг 2008, 03:22

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

#6 Сообщение Basileos » 28 сен 2011, 02:01

Сегодня что, день археолога?

Аватара пользователя
pashan
Сообщения: 1606
Зарегистрирован: 09 янв 2008, 13:56

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

#7 Сообщение pashan » 29 сен 2011, 16:01

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

Volochinuk
Сообщения: 29
Зарегистрирован: 07 май 2014, 12:54

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

#8 Сообщение Volochinuk » 11 ноя 2014, 15:27

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

Аватара пользователя
LuckyOne [away]
Сообщения: 4466
Зарегистрирован: 14 сен 2012, 16:52

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

#9 Сообщение LuckyOne [away] » 11 ноя 2014, 15:38

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

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

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

Ism
Сообщения: 314
Зарегистрирован: 13 фев 2010, 08:46
Откуда: Дубна
Контактная информация:

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

#10 Сообщение Ism » 11 ноя 2014, 17:43

Тогда надо запретить использование любого типа алгоритмов сортировки=)
Linux laptop 3.13.0-35-generic Ubuntu
Gnome, Tmpk, Tp-Link(WiFi), Dvb(36E)

Аватара пользователя
Ega23
Сообщения: 18260
Зарегистрирован: 22 окт 2008, 09:01

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

#11 Сообщение Ega23 » 11 ноя 2014, 17:46

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


Аватара пользователя
LuckyOne [away]
Сообщения: 4466
Зарегистрирован: 14 сен 2012, 16:52

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

#13 Сообщение LuckyOne [away] » 11 ноя 2014, 20:10

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

Аватара пользователя
Ega23
Сообщения: 18260
Зарегистрирован: 22 окт 2008, 09:01

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

#14 Сообщение Ega23 » 11 ноя 2014, 20:27

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

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

Аватара пользователя
SaaBaka
Сообщения: 4417
Зарегистрирован: 14 апр 2008, 14:54
Откуда: Laniakea Supercluster

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

#15 Сообщение SaaBaka » 11 ноя 2014, 21:23

Тоже мне, бином Ньютона. Обычное сложение с переносом (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), а на языке более высокого уровня надо огород городить.

Аватара пользователя
LuckyOne [away]
Сообщения: 4466
Зарегистрирован: 14 сен 2012, 16:52

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

#16 Сообщение LuckyOne [away] » 11 ноя 2014, 22:38

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

Аватара пользователя
Ega23
Сообщения: 18260
Зарегистрирован: 22 окт 2008, 09:01

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

#17 Сообщение Ega23 » 11 ноя 2014, 22:45

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

Аватара пользователя
SaaBaka
Сообщения: 4417
Зарегистрирован: 14 апр 2008, 14:54
Откуда: Laniakea Supercluster

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

#18 Сообщение SaaBaka » 11 ноя 2014, 22:56

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

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

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

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

Аватара пользователя
Ega23
Сообщения: 18260
Зарегистрирован: 22 окт 2008, 09:01

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

#19 Сообщение Ega23 » 11 ноя 2014, 23:11

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

Аватара пользователя
SaaBaka
Сообщения: 4417
Зарегистрирован: 14 апр 2008, 14:54
Откуда: Laniakea Supercluster

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

#20 Сообщение SaaBaka » 11 ноя 2014, 23:16

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

Аватара пользователя
Ega23
Сообщения: 18260
Зарегистрирован: 22 окт 2008, 09:01

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

#21 Сообщение Ega23 » 11 ноя 2014, 23:22

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

const
c = 1;

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

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

Аватара пользователя
SaaBaka
Сообщения: 4417
Зарегистрирован: 14 апр 2008, 14:54
Откуда: Laniakea Supercluster

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

#22 Сообщение SaaBaka » 11 ноя 2014, 23:29

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

Аватара пользователя
LuckyOne [away]
Сообщения: 4466
Зарегистрирован: 14 сен 2012, 16:52

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

#23 Сообщение LuckyOne [away] » 11 ноя 2014, 23:32

Устал сегодня, лень писать самому. Отделаюсь копипастой :)

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

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, исключительно вычитания и больше-меньше. Причем кроссплатформенные :)

Аватара пользователя
Ega23
Сообщения: 18260
Зарегистрирован: 22 окт 2008, 09:01

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

#24 Сообщение Ega23 » 11 ноя 2014, 23:36

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

Аватара пользователя
SaaBaka
Сообщения: 4417
Зарегистрирован: 14 апр 2008, 14:54
Откуда: Laniakea Supercluster

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

#25 Сообщение SaaBaka » 11 ноя 2014, 23:39

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

Ответить

Вернуться в «Программирование»