Программерские задачки - Страница 3 - 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. Вы ещё не голосовали в этом опросе

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

Цитата:
Сообщение от Parad0
Alex Thresher
Вот еще вопрос: потоки у меня "соревнуются". Сделал с использованием семафора.
Можно так?
Если ты ограничиваешь доступ к этой переменной... То есть мешаешь тредам мешать друг другу... То результат предсказуем: всегда должно получаться (начальное i)+20+20. Вся фишка в том, что потоки могут друг другу мешать.

Цитата:
Сообщение от Parad0
Ну сделаю несколько тестовых прогонов А там уже буду смотреть на распределение этой величины)))
Я все же не совсем понял,нужно решение? Или ответил-забыли?
Скорее, попробовал свои силы, узнал для себя что-то новое, и не забыл, а отложил в копилку полезных знаний Сам по себе ответ на 3-ю и 4-ю задачи никакой ценности не представляет: ну какая может быть ценность в двух диапазонах целых абстрактных чисел? Решение, с точки зрения кода, тоже несущественно, ибо зависит от многих параметров, в том числе компилятор, операционка, погода и т. д.. А вот проиллюстрированная этим решением концепция поможет лучше программировать в будущем По крайней мере, я надеюсь на это


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

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

Цитата:
А вот проиллюстрированная этим решением концепция поможет лучше программировать в будущем Smile По крайней мере, я надеюсь на это
Согласен.

А вот с двухпроцессорной машинкой все же не ясно.
Да, и еще если я создаю два потока, как быть уверенным, что они запустятся на разных процессорах?
Или ОС сама это сделает?



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

Alex Thresher
Насчет мешающих друг другу потоков - концепция инверсии приоритетов знакома?
Вот там, даже если потоки имеют разные уровни приоритетности, в результате взаимных синхронизаций, управление получает не та ветвь исполнения, которая должна была бы получить из соображений приоритетности, а другая, с более низким приоритетом.
Сам в реальности такое наблюдал. Жалкое зрелище. Особенно, если программа что-то вычисляет в течении месяца, а потом бум!..
И заново.



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

Цитата:
Сообщение от Parad0
А вот с двухпроцессорной машинкой все же не ясно.
Да, и еще если я создаю два потока, как быть уверенным, что они запустятся на разных процессорах?
Или ОС сама это сделает?
Насколько я знаю, гарантировать работу потоков на разных процессорах невозможно. Можно попытаться поиграть с приоритетом потока - выставить обоим потокам наивысший из всех возможных, и тогда у операционки не будет выбора, кроме как запустить оба разом, следовательно - на разных процессорах... Но фактически, поскольку изменение приоритета не мгновенно, столь которкий цикл с таким высоким приоритетом гарантированно завершится за то время, пока операционка будет менять приоритет второго потока. Так что этот способ почти наверняка даст последовательное, а не параллельное выполнение циклов. Вот если бы в циклах было не двадцать итераций, а двести миллиардов...

Так что не стоит предполагать, что потоки гарантированно выполняются на разных процессорах.


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

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

Цитата:
Сообщение от Parad0
Alex Thresher
Насчет мешающих друг другу потоков - концепция инверсии приоритетов знакома?
Вот там, даже если потоки имеют разные уровни приоритетности, в результате взаимных синхронизаций, управление получает не та ветвь исполнения, которая должна была бы получить из соображений приоритетности, а другая, с более низким приоритетом.
Сам в реальности такое наблюдал. Жалкое зрелище. Особенно, если программа что-то вычисляет в течении месяца, а потом бум!..
И заново.
Угу, знакома. Но это следствие работы алгоритма контроля за ресурсами: если процессу с высоким приоритетом требуется ресурс, занятый процессом с низким приоритетом, то логичным решением будет поднять приоритет уже бегущего процесса, чтобы он закончил свою работу и освободил ресурс побыстрее.


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

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

Вот код, выводящий в stdout сам себя. От дефайнов отказался, не понравилось Наверно можно оптимальнее, но я как-то не думал над этим.
Код:
#include <stdio.h>
#include <string.h>
char* p9 = "char* p%d = %c%s%c;%c";
char* p0 = "%s%c";
char* p1 = "char* x%d = %c%s%c;%c";
char* x0 = "#include <stdio.h>";
char* x1 = "#include <string.h>";
char* x2 = "\
int main(){\
  printf(p0,x0,13);\
  printf(p0,x1,13);\
  printf(p9,9,34,p9,34,13);\
  printf(p9,0,34,p0,34,13);\
  printf(p9,1,34,p1,34,13);\
  printf(p1,0,34,x0,34,13);\
  printf(p1,1,34,x1,34,13);\
  printf(p1,2,34,x2,34,13);\
  printf(p0,x2,13);\
  return 0;\
  }";
int main(){
  printf(p0,x0,13);
  printf(p0,x1,13);
  printf(p9,9,34,p9,34,13);
  printf(p9,0,34,p0,34,13);
  printf(p9,1,34,p1,34,13);
  printf(p1,0,34,x0,34,13);
  printf(p1,1,34,x1,34,13);
  printf(p1,2,34,x2,34,13);
  printf(p0,x2,13);
  return 0;
  }
Проверял в BC5. После первого запуска выстроится в длинные строки, но это так, лирика.


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

А по последним 2-м задачам, в условиях "сферического коня в вакууме", т.е. абстрактный проц, абстрактная ось, можем получить любой результат от 21 до 41.


Ответить с цитированием
  (#38) Непрочитано
фильтикультяплинивик
grand Master
Аватар для DeadMeat
Сообщений: 3,487
Регистрация: 28.09.2004
Адрес: Нальчик
Возраст: 36
Репутация: 32 Рейтинг
14.11.2007, 23:50

Под виндой переключить тред на нужную голову можно одной командой (SetAffinityMask, если мне склероз не изменяет). Под никсами... хез.
Я как то читал статью про многопоточность и практику ее применения в геймдевелопинге. Так вот фигня это все, если нет реально двух процев (НТ тоже фигня, ибо это виртуальные процы). Когда проц один, то выйгрыша от многопоточности фактически нет (1-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.
Ответить с цитированием
  (#39) Непрочитано
Священная инквизиция.
grand Master
Сообщений: 6,748
Регистрация: 20.10.2004
Репутация: 409 Рейтинг
14.11.2007, 23:58

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



Ответить с цитированием
  (#40) Непрочитано
фильтикультяплинивик
grand Master
Аватар для DeadMeat
Сообщений: 3,487
Регистрация: 28.09.2004
Адрес: Нальчик
Возраст: 36
Репутация: 32 Рейтинг
15.11.2007, 07:12

AXMED
Ой... Ненавижу задачки с олимпиад..


"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.
Ответить с цитированием
  (#41) Непрочитано
grand Master
Сообщений: 1,049
Регистрация: 18.02.2007
Репутация: 76 Рейтинг
15.11.2007, 10:49

Еще 5 копеек. Я все-таки проверил как компилится i++; (i - глобальная переменная). Вот результат:

BC 5.02 (одна инструкция)
Код:
inc dword ptr [edx]
VC 6.0 (три инструкции)
Код:
mov ecx, dword ptr [00405030]
add ecx, 00000001            
mov dword ptr [00405030], ecx
GCC 3.4.2 (одна инструкция)
Код:
inc dword ptr [00402000]


Ответить с цитированием
  (#42) Непрочитано
Мастер
Аватар для Alex Thresher
Сообщений: 836
Регистрация: 02.08.2007
Адрес: Израиль
Репутация: 56 Рейтинг
Ну что, други, начнём смотреть решения? - 15.11.2007, 14:35

Итак, решения:
  1. Задача № 1:
    (Напомню условие - надо было написать программу, которая будет компилироваться, но при запуске будет "вылетать").

    Ничего более короткого, чем это, я пока не видел:
    Код:
    int main(){return main();}
    Гарантирован stack overflow.
  2. Задача № 2:
    (Надо было написать программу, которая выводит сама себя).

    Программа, выводящая самоё себя, называется Quine. На самом деле, таких программ есть куча. Они написаны практически на любом языке, кроме, разве что, COBOL`а (либо я таких программ на COBOL`е просто не нашёл). Есть даже quine`ы на Brain****. Одно из самых больших собраний таких программ в Интернете находится здесь. Примеры для каждого конкретного языка каждый может посмотреть сам, но pumpkin правильно понял основной принцип построения такой программы.

    Однако quine, ставший лауреатом международного конкурса "International Obfuscated C Code Contest" в 1994 году, поразителен настолько, что многие программисты решили вытатуировать исходники этой программы у себя на лбу.

    Код этой программы:
    Код:
    
    
    Синтакс языка С не запрещает существование пустых файлов. Кроме того, существуют компиляторы, которые превратят пустой файл в программу, не делающую ничего. В любом случае, абсолютное большинство *NIX-cистем при попытке запустить программу, не имеющую входной точки (функции main в терминологии С), просто выйдут, не сообщив об ошибке, потому что, строго говоря, ошибки нет: программа, которая ничего не делает, завершила свою работу, сделав ничего. Правда, статус работы (переменная $status) при этом будет равным 1.

    Вот как это выглядит на AIX 5:
    Код:
    > touch test.c                           <-- Создали файл-"исходник"
    > wc test.c
           0       0       0 test.c          <-- Проверка - он и правда пустой
    > mv test.c test                         <-- "Компиляция"
    > chmod 777 test                         <-- Делаем его исполняемым
    > echo $status                           <-- Проверка статуса до запуска
    0
    > test                                   <-- Запуск программы
    >                                        <-- Добавленный мной перевод строки
    > echo $status                           <-- Проверка статуса после запуска
    1
    То есть "программа" test работает, как запланировано (никак). Более того, она выводит в stdout свой собственный исходный код (исходного кода нет, а она ничего не выводит, так что вполне можно сказать, что она выводит свой исходный код). Поэтому она полностью отвечает требованиям второй задачи.

    Это - самый маленький из всех возможных quine`ов.


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

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

Продолжение решений:
Задача № 4:
(Условие: есть общедоступная обнулённая переменная и цикл на 20 итераций. Цикл запускается двумя потоками на однопроцессорной машине. Каков диапазон возможных значений переменной?)

На RISC-процессоре код i++ будет записан тремя инструкциями ассемблера: "считать значение переменной из памяти", "увеличить значение", "записать в память". Как убедительно доказал pumpkin, и на CISC-процессоре тоже вполне могут получиться три инструкции ассемблера; зависит от компилятора. Context switch (смена исполняемого потока) может случиться в любой момент, между любыми двумя инструкциями.

Самый проблематичный сценарий следующий (между каждыми двумя последовательными пунктами выполняется context switch):
  1. Поток А считывает значение переменной и получает 0.
  2. Поток Б считывает значение переменной и тоже получает 0.
  3. Поток А выполняет 19 итераций цикла без помех. В конце в переменную записывается число 19.
  4. Поток Б выполняет одну итерацию и перезаписывает содержимое ячейки памяти числом 1.
  5. Поток А выполняет чтение из памяти в процессе 20-й итерации и читает число 1.
  6. Поток Б выполняет 20 итераций без помех и записывает в память число 20.
  7. Поток А заканчивает последнюю итерацию и записывает в память число 2.
Итого: диапазон возможных значений переменной после выполнения этого куска кода - от 2 до 40.

Мораль: при программировании в многопоточной среде любые переменные, доступные из нескольких потоков, должны защищаться семафорами, mutex`ами и тому подобной гадостью.

Задача № 3:
(То же условие, что и в задаче № 4, только процессоров в машине два).

Поскольку условием не дано никаких гарантий, что потоки будут запущены на разных процессорах, задача № 3 в общем случае сводится к задаче № 4.

Мораль: даже если в машине гарантированно есть много процессоров, при отсутствии других условий "семафорить" всё равно надо так, как если бы процессор был один.


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

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

Позже добавлю ещё несколько задач.


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

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

Цитата:
Сообщение от Alex Thresher
Ничего более короткого, чем это, я пока не видел:
Код:
int main(){return main();}
Пробовал, BC5 (другого не было под рукой) выдавал ошибку: "Bla-bla сan not be called within чего-то там".


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


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

Опции темы

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

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

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