LINUX.ORG.RU

Узнать, содержится ли один диапазон в другом на Си

 , ,


1

4

Сразу скажу что задача можно считать учебная и ответ на неё многих может показаться банальным, но мне интересно как бы вы её решили.

Условие очень простое: выражение is_contained(h0, hlen, q0, qlen) должно возвращать 1, если диапазон под вопросом (question - q), начинающийся включительно с q0 и занимающий всего qlen индексов, полностью содержится в диапазоне (have - то что имеется), начинающимся включительно с h0 и имеющим длину в hlen индексов, и должно возвращать 0 во всех других случаях. Оба диапазона относятся к индексам некоего массива или смещениям байт в файле, при том что файл целиком влез в аллоцированный блок памяти процесса в виде того же массива.

Вопрос: написать синтаксически корректную (допустим C89) реализацию функции is_contained(), такую чтобы всегда отдавала правильный результат, при этом не содержала лишнего кода и не требовала линковки с чем-то ещё, включая libc, для работы (но содержимым C89-стандартных (только их) .h файлов пользоваться можно, если оно не приводит к импорту символов извне).

Условие именно такое как я написал, никакие уточнения не предполагаются. Если считаете что условие где-то двусмысленное - дополняйте его как хотите (не противореча исходным утверждениям).

★★★★★

Последнее исправление: firkax (всего исправлений: 5)

Ответ на: комментарий от wandrien

ИМХО. Никакая оптимизация не имеет права искажать результат работы написанного алгоритма, это для меня аксиома.

Пишите письма в комитет.

Не, спасибо, я не на столько крут, как вы.

Vic
()
Последнее исправление: Vic (всего исправлений: 1)
Ответ на: комментарий от Vic

В том и дело, что она не искажает.

В Си в общем случае x++; НЕ означает что надо прибавить единицу к x в машинном представлении. Оно означает «прибавь единицу, если оно не переполнится, иначе делай что хочешь». Но ты упорствуешь в своём альтернативном понимании языка а потом удивляешься почему реализация (компилятор) ему не соответствует.

А с твоей логикой можно и до осуждения такого кода дойти:

x = y+1;
y = 5;
printf("x = %d\n", x);
и предъявлять претензии, что оно не выдало «правильный» ответ 6, ведь в исходнике написано что x=y+1 и что y=5. Разумеется наплевав на то, что знак = в Си не означает постулирование равенства (как в математике), а означает запись в переменную слева от него.

firkax ★★★★★
() автор топика
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от firkax

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

Поэтому делаем так:

  • сначала проверяем что все 4 аргумента >= 0 иначе ну его нафиг
  • если q0 < h0 тоже ну его нафиг, иначе можно посчитать q0 - h0
  • если qlen > hlen то ну его нафиг, иначе можно посчитать hlen - qlen
  • если после этого (q0 - h0) <= (hlen - qlen) значит влезло а если нет то нет

Тред не читал.

anonymous
()