Ответ на »сообщение 2095« (Geniepro)
___________________________
Однако у вас прорва свободного времени. :))
Я даже в субботу вынужден заниматься идиосинкразиями различий IE и Firefox. Нужно поддерживать оба браузера :(((

Ответ на »сообщение 2095« (Geniepro)
___________________________

В связи с этим прошу модераторов удалить моё предыдущее сообщение

Извиняюсь, но я попарился с ссылкой.
Прошу модераторов удалить моё сообщение № 2094 в этой теме.

Обнаружил странный глюк, связанный с разным пониманием кодировок ANSI/UTF-8 разными трансляторами Хаскелла, исправил и обновил код на Хаскелле.
В связи с этим прошу модераторов удалить моё предыдущее сообщение

ЗЫ. Проблема была из-за того, что функция openFileC имела последнюю букву С кириллическую, а не латинскую. Начертание у них одинаковое, а коды - разные. WinHUGS принимал файл в кодировке ANSI без проблем, GHC отвергал. В кодировке UTF-8 - наоборот, GHC нормально принимал, а WinHUGS ругался...
ЗЗЫ. Мдя, всё-таки идентификаторы должны записываться латинницей!!!
[BR]
А вот и примерное решение этой задачи на Хаскелле.
Поскольку я всего лишь "a little haskeller", то наверняка этот код можно улучшить, в смысле упростить. Но, в принципе, работает...

module ACM_2007_A where

import IO

{-------------------------------------------------------------------------------
--                  Номер  Гр.кр.  Гр.кр.  Гр.кр.
--                  строки  родит.  родит.  ребёнка
-}
type TestCaseStr  =        (String, String, String)
type TestCaseStrLn = (Int,  TestCaseStr)

type TestCase      =        (SetABO, SetABO, SetABO)
type TestCaseLn    = (Int,  TestCase)

type SetABO        = [String]

--------------------------------------------------------------------------------

main = do fromHandle  <- openFileC "blood.in" ReadMode
          contents    <- hGetContents fromHandle
          showTestCaseLn $ process $ convert contents -- собственно расчёт
          hClose fromHandle

--------------------------------------------------------------------------------

openFileC :: String -> IOMode -> IO Handle
openFileC name mode =
    do  catch (openFile name mode)
              (\_ -> error $ "Cannot open file "++ name ++ "\n")

{-------------------------------------------------------------------------------
-- Преобразовать содержимое входного файла в список [TestCaseStrLn]
-}
convert :: String -> [TestCaseStrLn]
convert s = takeWhile (\(_, tc) -> tc /= the_END)
                      (map  strs'to'TestCaseLn
                            (zip [1..] (str'to'strs s)))
  where
    {-----------------------------------------------------------------
    -- Преобразовать строку символов с разделителями \n в список строк
    -- с учётом возможных пустых строк. Пустые строки отсеять.
    -}
    str'to'strs :: String -> [String]
    str'to'strs s = to_strs s [] []
      where
        to_strs    [ ]    v w = filter ([]/=) $ reverse (reverse v : w)
        to_strs ('\n':cs) v w = to_strs cs  []  (reverse v : w)
        to_strs (  c :cs) v w = to_strs cs (c:v)        w

    {--------------------------------------------------------------------------
    -- Преобразовать строку вида "O+ O- ?" в кортёж типа ("O+", "O-", "?")
    -- с учётом неопределённого количества пробелов между группами и после них.
    -- Все пробелы отсеять.
    -}
    strs'to'TestCaseLn :: (Int, String) -> TestCaseStrLn
    strs'to'TestCaseLn (ln, s) = to_tc s True [] []
      where
        to_tc    [ ]      _  v w = tc $ filter (""/=) $ reverse (reverse v : w)
        to_tc (' ':cs) True  v w = to_tc cs False  []  (reverse v : w)
        to_tc (' ':cs) False _ w = to_tc cs False  []          w
        to_tc ( c :cs)    _  v w = to_tc cs True  (c:v)        w

        tc [m, p, c] = (ln, (m, p, c))
        tc  _        = error $ "Incorrect number of blood types in line "
                            ++ show ln ++ ":\n\n" ++ s ++ "\n"

--------------------------------------------------------------------------------

the_END = ("E", "N", "D") -- Завершитель входного файла

allels'from'ABO "A"  = [ "A", "O" ]
allels'from'ABO "B"  = [ "B", "O" ]
allels'from'ABO "AB" = [ "A", "B" ]
allels'from'ABO "O"  = [ "O" ]

abo'from'allels "AA" = "A"
abo'from'allels "AO" = "A"
abo'from'allels "OA" = "A"
abo'from'allels "BB" = "B"
abo'from'allels "BO" = "B"
abo'from'allels "OB" = "B"
abo'from'allels "AB" = "AB"
abo'from'allels "BA" = "AB"
abo'from'allels "OO" = "O"

allels'from'Rh  "+"  = [ "+", "-" ]
allels'from'Rh  "-"  = [ "-" ]

rh'from'allels  "++" = "+"
rh'from'allels  "+-" = "+"
rh'from'allels  "-+" = "+"
rh'from'allels  "--" = "-"

all'blood'types      = [ abo ++ rh  | abo <- [ "A", "AB", "B", "O" ],
                                      rh  <- [ "-", "+" ]            ]

{----------------------------------------------------------------------
-- Отделить тип крови от резус-фактора
-- и выдать списки возможных аллелей группы и резус-фактора
-}
get_allels :: Int -> String -> (SetABO, SetABO)
get_allels _ (a:l:r:[]) = (allels'from'ABO (a:[l]), allels'from'Rh [r])
get_allels _  (a:r:[])  = (allels'from'ABO  ([a]),  allels'from'Rh [r])
get_allels ln    err    = error $ "Incorrect blood type in line "
                                ++ show ln ++ ":\n\n" ++ err ++ "\n"

{--------------------------------------------------------------
-- Отсеять повторяющиеся элементы в списке
-}
sieve :: (Eq a) => [a] -> [a]
sieve (x:xs) = sievet xs [x]
  where
    sievet  [  ]  w = reverse w
    sievet (y:ys) w = sievet ys (if y `elem` w then w else y:w)

{-------------------------------------------------------------------------------
-- В такой вот вид нужно перевести входные данные:
--
-- [ (1, ("O+",    "O-",    "?")),
--  (2, ("O+",    "?",    "O-")),
--  (3, ("AB-",  "AB+",  "?")),
--  (4, ("AB+",  "?",    "O+"))  ] -->
--
-- [ (1, (["O+"],  ["O-"],  ["O+", "O-"])),
--  (2, (["O+"],  ["A-", "A+", "B-", "B+", "O-", "O+"], ["O-"])),
--  (3, (["AB-"], ["AB+"], ["A+", "A-", "B+", "B-", "AB+", "AB-"])),
--  (4, (["AB+"], [],      ["O+"]))                                  ]
-}
process :: [TestCaseStrLn] -> [TestCaseLn]
process tcs = map (\(ln, var) -> (ln, calculate ln var)) tcs
  where
    calculate :: Int -> TestCaseStr -> TestCase
    calculate ln ( m,  p, "?") = ([m], [p],  calc_child ln m p)
    calculate ln ( m, "?", c ) = ([m], calc_parent ln m c, [c])
    calculate ln ("?", p,  c ) = (calc_parent ln p c, [p], [c])
    calculate ln      err      = error $ "Incorrect test case in line "
                                      ++ show ln ++ ":\n\n" ++ show err ++ "\n"

    {--------------------------------------------------------------------------
    -- Получить списки возможных аллелей родителей
    -- и составить из них список возможных типов крови ребёнка
    -}
    calc_child :: Int -> String -> String -> SetABO
    calc_child ln mama papa = [ abo ++ rh | abo <- c_abo, rh <- c_Rh ]
      where
        (m_abo, m_Rh) = get_allels ln mama
        (p_abo, p_Rh) = get_allels ln papa
        c_abo = sieve $ map abo'from'allels [ m ++ p | m <- m_abo, p <- p_abo ]
        c_Rh  = sieve $ map  rh'from'allels [ m ++ p | m <- m_Rh,  p <- p_Rh  ]

    {----------------------------------------------------------------------------
    -- Получить типы крови одного родителя и ребёнка
    -- и составить список возможных типов крови второго родителя.
    -- Для этого просматриваем список всех возможных типов крови второго родителя
    -- и отбрасываем те типы, которые не могут в сочетании с типом первого
    -- родителя дать нужный тип крови ребёнка.
    -}
    calc_parent :: Int -> String -> String -> [String]
    calc_parent ln parent child = filter possible all'blood'types
      where
        possible bt = child `elem` (calc_child ln parent bt)

{-------------------------------------------------------------------------------
-- Вот так нужно распечатать:
-- (перед закрывающей фигурной скобкой пробел ставить на самом деле не нужно,
-- просто конфликтует с закрывающим символом комментария в Хаскелле)
--
-- Case 1: O+ O- {O+, O- }
-- Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
-- Case 3: AB- AB+ {A+, A-, B+, B-, AB+, AB- }
-- Case 4: AB+ IMPOSSIBLE O+
-}
showTestCaseLn :: [TestCaseLn] -> IO ()
showTestCaseLn tcs = foldr (>>) (return ()) $ map (putStrLn.show_tc) tcs
  where
    show_tc :: TestCaseLn -> String
    show_tc (ln, (m, p, c)) = "Case " ++ show ln ++ ":" ++ show_SetABO m
                                      ++ show_SetABO p  ++ show_SetABO c
      where
        show_SetABO [ ] = " IMPOSSIBLE"                -- Нет  вариантов
        show_SetABO [a] = ' ':a                        -- Один вариант
        show_SetABO set = " {" ++ show_set set ++ "}"  -- Куча вариантов
          where
            show_set  [c]    = c
            show_set (c:cs)  = c ++ ',':' ':show_set cs

Входной файл blood.in :

O+ O- ?
O+ ? O-
AB- AB+ ?
AB+ ? O+
E N D

Результат:

Case 1: O+ O- {O+, O-}
Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
Case 3: AB- AB+ {A+, A-, AB+, AB-, B+, B-}
Case 4: AB+ IMPOSSIBLE O+

Эталонный результат:

Case 1: O+ O- {O+, O-}
Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
Case 3: AB- AB+ {A+, A-, B+, B-, AB+, AB-}
Case 4: AB+ IMPOSSIBLE O+

Результаты выводятся не совсем в том порядке, что в примере ( {A+, A-, AB+, AB-, B+, B-} вместо {A+, A-, B+, B-, AB+, AB-} ), но, как я понимаю, это не критично, поскольку в условиях задачи не сказано, как именно сортировать выходные данные, просто сказано, что формат вывода должен быть похожим на пример.

По предложению Руслана Богатырёва в соседней теме

Первая задача из списка задач олимпиады %url[ACM ICPC 2007 Final] http://icpc.baylor.edu/icpc/Finals/2007WorldFinalProblemSet.pdf
"Problem A+. Consanguine Calculations"

Задача А+

Анализ кровнородственности

Входной файл: blood.in

  Кровь любого человека имеет 2 маркера, называемых ABO-аллелями. Каждый маркер представляется одной из трёх букв: A, B или O. Это даёт шесть возможных комбинаций аллелей, которые могут быть у человека, каждая из которых может характеризовать группу крови ABO этого человека.

Комбинация    Группа крови ABO
~~~~~~~~~~    ~~~~~~~~~~~~~~~~
    AA                A
    AB                AB
    AO                A
    BB                B
    BO                B
    OO                O

  Также каждый человек имеет две аллели резус-фактора крови Rh, представленных символами + и -. У тех, у кого Rh-положительный (Rh+), имеется от одной до двух аллелей +. У тех, у кого Rh-отрицательный, обе аллели всегда -.

  Тип крови человека - это комбинация группы крови ABO и резус-фактора Rh. Тип крови записывается обозначением группы крови с суффиксом + или -, обозначающим резус-фактор, например, A+, AB-, O-.

  Типы крови наследуются - каждый биологический родитель передаёт своему ребёнку одну ABO-аллель (случайно выбираемую из его двух) и одну аллель резус-фактора. Таким образом, две ABO-аллели и две аллели резус-фактора родителей определяют тип крови ребёнка. Например, если оба родителя имеют тип крови А-, то ребёнок может иметь любой из двух типов: А- или О-. У родителей с типами А+ и В+ ребёнок может иметь любой тип крови.

  В этой задаче даются типы крови обоих родителей или одного из родителей и ребёнка; требуется получить (возможно пустое) множество типов крови, которые могут быть у ребёнка или у другого родителя.

  Примечание: прописная буква "О" используется в этой задаче для обозначения типа крови, а не цифры 0.

  Входные данные:
  ~~~~~~~~~~~~~~~

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

  За последний тестовым вариантом следует строка с буквами "E", "N" и "D", разделёнными пробелами.

  Выходные данные:
  ~~~~~~~~~~~~~~~~

  Для каждого тестового варианта требуется распечатать номер теста (начинающегося с 1) и типы крови родителей и ребёнка. Если нет возможного для родителя типа крови, распечатать “IMPOSSIBLE”. Если для родителей или ребёнка возможны несколько вариантов типов крови, распечатать все возможные варианты в виде списка значения, разделённых запятыми, и заключённого в фигурные скобки.

  Пример вывода иллюстрирует несколько выходных форматов. Ваш формат вывода должен быть похожим.

  Sample Input        Output for the Sample Input
  ~~~~~~~~~~~~        ~~~~~~~~~~~~~~~~~~~~~~~~~~~

  O+ O- ?            Case 1: O+ O- {O+, O-}
  O+ ? O-            Case 2: O+ {A-, A+, B-, B+, O-, O+} O-
  AB- AB+ ?          Case 3: AB- AB+ {A+, A-, B+, B-, AB+, AB-}
  AB+ ? O+            Case 4: AB+ IMPOSSIBLE O+
  E N D

Некий Joel Reymont как-то рассказывал, почему он любит Хаскелл...

Основное влияние на него оказала статья Саймона Пейтона Джонса Composing contracts: an adventure in financial engineering

А ещё, Пейтон Джонс (один из отцов-основателей Хаскелла) потратил своё время на то, что бы объяснить ему (Джоэлу) по телефону работу с конструкторами в Хаскелле и с Shared Transactional Memory (STM).

Вот так Хаскелл и зарабатывает народную любовь! :о))

Ответ на »сообщение 2087« (Geniepro)
___________________________
tail call, если сразу после него не идет ret -  обычный call.

Ответ на »сообщение 2088« (Geniepro)
___________________________


Похоже, в Ваших программах точно багов нет - одни лишь только недокументированные возможности... :о))


Я довольно много писал на C++, с проблемами из-за оптимизации (и переупорядочивания инструкций в частности) ни разу не сталкивался, в том числе и в многопоточном коде. С ошибками самих оптимизаторов сталкивался только пару раз - у борландовского компилятора и у VC6.


, пытаются пытаются изучать пути верификации С-программ ?..
Зря время только теряют...

Я тоже думаю, что это тупиковый путь.

Ответ на »сообщение 2088« (Geniepro)
___________________________

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

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

>>> Запрещены указатели на функции

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

Ответ на »сообщение 2086« (pepper)
___________________________

Ошибка в данном случае исключительно в твоей программе.

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

Похоже, в Ваших программах точно багов нет - одни лишь только недокументированные возможности... :о))

Программы на С++ неправильными быть не могут по определению, так как определения неправильных программ для С++ отсутствуют! :о))

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