Программерские задачки - Nalchik On Line - Форум Нальчика и КБР
Nalchik On Line - Форум Нальчика и КБР
Вернуться   Nalchik On Line - Форум Нальчика и КБР > Hard & Soft > Soft > Developing
Перезагрузить страницу Программерские задачки
Результаты опроса: Постить ещё задачки?
Нет 0 0%
Да 2 1.15%
Да, и задачи, не связанные с программированием, тоже 0 0%
Да, но не только для С, а и для других языков тоже 1 0.57%
171 98.28%
Голосовавшие: 174. Вы ещё не голосовали в этом опросе

Ответ
Опции темы
  (#1) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
Программерские задачки - 13.11.2007, 18:30

Для начала напишу три задачки, потом, по мере решения, буду добавлять ещё.

Решение писать на ANSI C, компилировать gcc, проверять работоспособность на *NIX, если в условии не указано иначе.
  1. Написать как можно более короткую программу, которая будет компилироваться без ошибок, но при запуске будет "вылетать" с ошибкой.
    Решение опубликовано здесь.
  2. Написать программу, выдающую в stdout собственные исходники. Имя файла с исходниками неизвестно.
    Решение опубликовано здесь.
  3. Дан следующий код:
    Код:
    int i = 1; 
    /* Здесь выполнение кода разделяется на 2 thread`а */
    /* Начинается тело цикла, повторяющегося 20 раз */
        i++;
    /* Заканчивается тело цикла */
    Этот код запускают на двухпроцессорной машине двумя разными потоками (threads, не processes). Каковы возможные значения i по окончании работы куска кода? Ни о каких способностях железа или операционки синхронизировать работу thread`ов неизвестно. Можно предположить, что каждый thread выполняет тело цикла 20 раз.
    Решение опубликовано здесь.
  4. Дан кусок кода:
    Код:
    int i = 0;
    /* Здесь выполнение кода разделяется на 2 thread`а */
    /* Начало цикла на 20 итераций */
      i++;
    /* Конец цикла на 20 итераций */
    Каковы возможные значения i при выполнении этого кода на однопроцессорной машине? Можно предположить, что каждый thread выполняет тело цикла ровно 20 раз. Ни о каких способностях железа или операционки синхронизировать работу thread`ов неизвестно.
    Решение опубликовано здесь.


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#2) Непрочитано
фильтикультяплинивик
grand Master
Аватар для DeadMeat
Сообщений: 3,492
Регистрация: 28.09.2004
Адрес: Нальчик
Возраст: 37
Репутация: 33 Рейтинг
13.11.2007, 19:05

1. В Сях не мастер, но в делфи это одна строка.
2. В теории это невозможно, если только сам исходник не сохранить как ресурс или просто в тело ЕХЕ файла (это я про вынь). Да и что называть исходником? Программа на АСМе тоже исходник программы на С.
3. Ну тут не однозначно само условие. Запускают ли треды с самого начала или только тело цикла помещено в тред? Сколько раз прокручиваются треды сами по себе? Да и все-таки это вынь или никс? Как определена эта переменная в них? Доступна ли она из каждого треда?

Ну это я так...
А по теме... давай много вопросов!!


"Mad girlfriend bug", is a bug whose immediate effect remains hidden - the app outwardly seems to function normally and tells you that everything is fine.
Ответить с цитированием
  (#3) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
13.11.2007, 19:52

DeadMeat
Ну, эт вы придираетесь, барин

Первая задача в С решается тоже одной строкой. Мой минимум - 26 символов. На самом деле, если компилятор нормальный, то ЛЮБУЮ программу можно написать одной строкой. Вон люди даунлоадеры с YouTube в одну строку пишут.

Исходник - это то, из чего путём компиляции, интерпретации или другим путём получается исполняемый файл. В данном случае язык разработки чётко определён - С. Если хочешь, можешь, конечно, и на ассемблере вставки в С писать, но, из собственного опыта, для решения этой задачи такие мощные средства не нужны. Кроме того, такая программа возможна, сам пару минут назад сделал. По секрету скажу, - на других языках такую программу тоже можно написать.

В тредах запускается цикл (aka инициализация переменной происходит до разделения на треды). Выключаются ли треды после выхода из цикла - неважно. Треды сами по себе прокручиваться не могут, они не циклы. Количество выдаваемого каждому треду времени определяет scheduler операционной системы, в качестве которой можно принять *NIX (но в Винде эффект абсолютно такой же, проверено). Над scheduler`ом власти нет. Переменная определена программистом как int в области данных, а не на стеке, что означает 32 бита, по-моему, в любой современной системе. А насчёт доступа к переменной из обоих тредов - я специально подчеркнул, что это не процессы, а именно треды...

Решения напишу в четверг.


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#4) Непрочитано
Мастер
Аватар для 44LSD
Сообщений: 221
Регистрация: 01.07.2007
Адрес: Одесса
Возраст: 33
Репутация: 1 Рейтинг
13.11.2007, 21:01

по 1) такой вариант подойдет?
Код:
main(){int(*f)()=0;f();}
Segmentation fault гарантирован
Ответить с цитированием
  (#5) Непрочитано
фильтикультяплинивик
grand Master
Аватар для DeadMeat
Сообщений: 3,492
Регистрация: 28.09.2004
Адрес: Нальчик
Возраст: 37
Репутация: 33 Рейтинг
13.11.2007, 21:15

А че делать.... вот такой я заковыристый.

1. Здесь опять пролетаемсс... (хотя деление на ноль можно еще, но тогда будет просто ошибка, а не вылет, насколько я понимаю С).
2. Ну пардон, тут все зависит от компилятора и вообще от его настроек да и от среды в целом (в плане оболочки в которой пишем). Если вся эта кухня сама не сохраняет исходник программы на том языке, на котором она создается (тобишь на С) в тело исполняемого файла, то откуда вы его возьмете? Поэтому я и сказал... что в теории это не возможно. В том смысле, если этого не сделать заранее. А про АСМ я сказал, что ведь можно получить исходник любой программы на АСМе.. А вот на уже более специфичном языке - проблема. Опять же объясню свою мысль. Откуда вы вытащите названия переменных и других "меток" (программы, функции и т.п.), если их нет? А это означает, что полученный исходник не является точной копией изначального исходника... Да и воссоздать обратный процесс перевода из языка низкого уровня в язык высокого (именно точный процесс.. т.е. грубо говоря перемотка) весьма проблемно. Разве нет? Соответственно задача в общем случае не решаема. А если это не важно (имена я имею ввиду), то можно поступить как дизасемблер. Т.е. по тому же принципу.
3. Ну уже понятней стало (да я такой... еще и не понятливый ко всему прочему). Да и "сами по себе" я не имел ввиду, что они себя сами прокручивают... Так что насчет "придираетесь"... И так что мы получаем. Запускается первый тред. Считывает значение ячейки (там 1), увеличивает его и записывает обратно (там 2). Теперь второй тред берет значение (там 2), увеличивает его и записывает обратно (там 3). Все замечательно, если они синхронизированы. А вот если: первый тред считывает значение 3, увеличивает, но записать не успевает потому что в это время второй тред считал, увеличил и записал туда следующее значение (4ку). Когда первый записывает значение, то он записывает тоже 4. Что получается? Один ход второго треда прошел впустую. Ну и так далее... Т.е. зависит от шедулера. Но это в случае однопроцессорной системы (т.е. два просто потока). Насколько я понимаю (а я часто ошибаюсь) в случае многопоцессорной системы (если второй тред запущен на второй голове) эта байда пашет одновременно. Значит в первом варианте может быть что угодно, но вроде как меньше 40, а во втором 20.

ЗЫ. Скорее всего много чего напутал, поэтому просьба не пинать. Я стеснительный.


"Mad girlfriend bug", is a bug whose immediate effect remains hidden - the app outwardly seems to function normally and tells you that everything is fine.
Ответить с цитированием
  (#6) Непрочитано
Священная инквизиция.
grand Master
Сообщений: 6,748
Регистрация: 20.10.2004
Репутация: 409 Рейтинг
13.11.2007, 23:14

Alex Thresher
Плиз, условие второй задачи перефразируй на Паскаль.



Ответить с цитированием
  (#7) Непрочитано
Священная инквизиция.
grand Master
Сообщений: 6,748
Регистрация: 20.10.2004
Репутация: 409 Рейтинг
13.11.2007, 23:31

И можно ли пользоваться директивами компилятора?



Ответить с цитированием
  (#8) Непрочитано
Священная инквизиция.
grand Master
Сообщений: 6,748
Регистрация: 20.10.2004
Репутация: 409 Рейтинг
14.11.2007, 00:04

1 задача:
Код:
begin
  runerror(100)
end.
на Паскале все просто :D



Ответить с цитированием
  (#9) Непрочитано
grand Master
Аватар для Parad0
Сообщений: 4,939
Регистрация: 01.10.2006
Репутация: 222 Рейтинг
14.11.2007, 00:44

Alex Thresher
Абсолютно согласен с DeadMeat по второму пункту.
Декомпиллировать в код Ассемблера еще возможно, а вот в в тот язык, на котором написана программа... Да еще и верно...

По третьему пункту...
Предположу, что приоритеты потоков равны (?)
Насчет одновременности работы - может быть.
Тогда значение будет равно 20.
На однопроцессорной системе ОСь может синхронизировать потоки, вплоть до взаимного исключения.
Сегодня проверю на однопроцессорной системе. Синхронизирую два потока. Посмотрим, что выйдет.


Ответить с цитированием
  (#10) Непрочитано
grand Master
Сообщений: 1,049
Регистрация: 18.02.2007
Репутация: 76 Рейтинг
14.11.2007, 08:13

1. Поиграться с кривыми адресами, как 44LSD сделал, там вместо 0 можно что-то другое поставить. Например main(){int(*f)()=(int(*)())4;f();} или main(){int x;int(*f)()=(int(*)())&x;f();}. Или такой вариант(в вантузе срабатывает): main(){printf(0)}, хотя здесь либа подтягивается.

2. По-моему здесь надо исходный код в дефайны засунуть. А ниже директивами прекомпилера вывалить для компиляции.

3. Теоретически должно быть что угодно, от 21 до 41, но фактически надо смотреть, что компилер сделал. i++ слишком короткий код (AFAIR одна инструкция), поэтому на 1 физическом процессоре рассинхронизации не произойдет и будет 41, а на 2-х физических - не уверен сходу, но думаю 21.

Может я ошибаюсь.


Ответить с цитированием
  (#11) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
14.11.2007, 09:30

Цитата:
Сообщение от 44LSD
по 1) такой вариант подойдет?
Код:
main(){int(*f)()=0;f();}
Segmentation fault гарантирован
Это не ANSI C По спецификации ANSI, программа должна возвращать целочисленный статус операционной системе. Так что добавляется как минимум int в начале и return в конце. Получаем 36 символов. Можно на целых 9 символов короче. Хотя идея хороша, я проверил - и правда не работает


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#12) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
14.11.2007, 09:40

Цитата:
Сообщение от Parad0
По третьему пункту...
[ . . . ] Сегодня проверю на однопроцессорной системе. Синхронизирую два потока. Посмотрим, что выйдет.
Это была четвёртая задача!!! Тот же самый код, но на однопроцессорной машине.

Ладно уж, пишу условие:

Задача 4.

Дан кусок кода:
Код:
int i = 0;
/* Здесь выполнение кода разделяется на 2 thread`а */
/* Начало цикла на 20 итераций */
  i++;
/* Конец цикла на 20 итераций */
Можно предположить, что каждый thread выполняет тело цикла ровно 20 раз. Каковы возможные значения i при выполнении этого кода на однопроцессорной машине? Ни о каких способностях железа или операционки синхронизировать работу thread`ов неизвестно.


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#13) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
14.11.2007, 09:58

Цитата:
Сообщение от AXMED
Alex Thresher
Плиз, условие второй задачи перефразируй на Паскаль.
На самом деле, условие остаётся тем же: написать программу, выводящую собственный исходный код. Пользоваться можно любыми средствами, лишь бы компилировалось и работало

Честно говоря, я не настолько силён в Паскале, чтобы знать, можно ли написать программу, печатающую собственный код. Пришлось немного порыться. Да, можно, правда, это сложнее, чем в С. Больше того, есть программа на Паскале, печатающая собственные исходники и написанная в виде палиндрома (вот ведь нечего было делать человеку! ).


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
  (#14) Непрочитано
Священная инквизиция.
grand Master
Сообщений: 6,748
Регистрация: 20.10.2004
Репутация: 409 Рейтинг
14.11.2007, 10:47

Alex Thresher
Т.е., считается, что файла с исходниками у нас вообще нету? Только exe?
Или можно предположить, что я могу эти исходники найти?



Ответить с цитированием
  (#15) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 843
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
14.11.2007, 10:49

Цитата:
Сообщение от AXMED
1 задача:
Код:
begin
  runerror(100)
end.
на Паскале все просто :D
Если я не ошибаюсь, то runerror сам сообщает об ошибке. То есть эта программа, несмотря на то, что вылетает, всё равно работает, как запланировано программистом, ибо вылетает с помощью специального вызова. А в задаче предполагается, что в программе ни самих ошибок, ни вызовов ошибок нет. Что-нибудь вроде деления на ноль или обращения к неверному адресу памяти, как в ответе 44LSD. Чтобы операционка программу прихлопнула.


То, что ваше мнение не совпадает с моим, лишний раз доказывает, что оно у вас ошибочное.

Ответить с цитированием
Ответ


Вернуться Nalchik On Line - Форум Нальчика и КБР > Hard & Soft > Soft > Developing

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Логические задачки Аха БеседКа 1329 31.08.2020 17:21
В школьных классах решают межнациональные задачки и отвечают на межэтнические вопросы никанет Новости 103 21.12.2013 11:04
Включаем мозги... Решаем задачки dzora93 БеседКа 17 24.12.2011 01:09
Веселые задачки AcedTect Флудилка 54 30.04.2011 08:04