Страницы: 1
RSS
Задачка
 
Если кто-то скучает, поставьте числа вместо многоточий:
Цитата
В этом предложении цифра 0 встречается ... раз, цифра 1 - ... раз, цифра 2 - ... раз, цифра 3 - ... раз, цифра 4 - ... раз, цифра 5 - ... раз, цифра 6 - ... раз, цифра 7 - ... раз, цифра 8 - ... раз, цифра 9 - ... раз
Есть как минимум два решения :)
Я решения нашел, алгоритм не придумал кроме как перебор. Но он должен же быть! :) Вдруг кто его опишет? :)
F1 творит чудеса
 
Ох ) давненько я такого не видел )) как то занимался таким во время учёбы. это из серии "Само описывающие тексты".
Как составить так и решить возможно только методом перебора.
И чем больше длина конструкции тем больше займёт времени.

Ответ, не смотрите кто хочет сам решить
Изменено: Wild.Godlike - 14.02.2020 14:05:55
 
Wild.Godlike, оно, ага. а второе решение? :) оно мне нравится гораздо больше, оно красивее
F1 творит чудеса
 
Максим Зеленский,
Ответ, не смотрите кто хочет сам решить


P.s. вот тут очень занятная статья на эту тему, простым языком )

Когда учился, нам профессор на втором курсе, на кафедре, примерно так же преподнёс данную задачку, причём не рассказывая вообще никакого контекста и смысла задачи)
Уточнил только одно.
Тем кто решит не перебором, обещал автоматом зачёт со второго по четвертый курс и освобождение от занятий) в итоге я закончил учёбу в 2013 но ответа ни кто не нашел)
Изменено: Wild.Godlike - 14.02.2020 14:52:41
 
Wild.Godlike, супер :)
F1 творит чудеса
 
Очень долго писал код, который очень быстро находит ответ, а он в заданных мною пределах один, блин. А под "красивый вариант" надо переписывать ((
Скрытый текст


Скрытый текст
Изменено: Wiss - 14.02.2020 16:59:43
Я не волшебник, я только учусь.
 
Wiss, о, код... супер!
F1 творит чудеса
 
а я пока стесняюсь код писать, а то придёт МСН и всем ататушки сделает со своей комбинаторикой  :D
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Максим Зеленский, спасибо за похвалу, но мне пока не нравится. Я там с граничными показателями накосячил. С одним - точно (поэтому второй ответ не получил), а во втором я теперь тоже стал сомневаться (забыл, чем я его обосновывал).
Я не волшебник, я только учусь.
 
Максим Зеленский,
Я это вижу как-то так в виде рекурсии:
Код
let
    source = let list = {"0".."9"} in Table.FromColumns({list,List.Repeat({"1"},List.Count(list))},type table [d=text,c=text]),
    recur = (tab) =>
    let
        tab1 = Table.ReplaceValue( 
            tab, 
            0, 
            each [d], 
            (x,y,z) => Text.From( 
                List.Count( 
                    List.Select( 
                        List.Combine( 
                            List.Transform( 
                                tab[d] & tab[c], 
                                each Text.ToList(_) 
                            )
                        ), 
                    each _ = z ) 
                ) 
            ), 
            {"c"}
        )
    in
        if tab1[c] = tab[c] then tab else @recur( tab1 )
in
    recur( source )
Вот горшок пустой, он предмет простой...
 
PooHkrd, а у Вас получается один ответ или больше? Не могу проверить - офиса под рукой нет.
Я не волшебник, я только учусь.
 
Wiss, один, который "красивый". Вот только на диапазоне 0..8 уходит в нирвану. Щас ручками разложу, гляну куда он там упирается
Вот горшок пустой, он предмет простой...
 
Цитата
PooHkrd написал:
который "красивый".
ВАУ! Пошёл перегружаться в винду и разбирать по косточкам Ваше чудо. Странно, что именно "красивый первым выходит".
Я не волшебник, я только учусь.
 
Цитата
Wiss написал:
Не могу проверить - офиса под рукой нет.
в понедельник весь офис решает задачу  :D
По вопросам из тем форума, личку не читаю.
 
В общем диапазон 0..8 данным алгоритмом в PQ вешается - переполнение стека. Ленивка растудыть его в коромысло.
Вот горшок пустой, он предмет простой...
 
Все таки рекурсия в PQ медленная, переделал цикл на генератор и там обнаружил, что начиная с 8-ой итерации таблица начинает поочередно принимать 2 одинаковых состояния и цикл уходит в небо за табором:
Вот они, эти коварные таблицы

Код
let
    source = Table.Buffer( let list = {"0".."9"} in Table.FromColumns({list,List.Repeat({"1"},List.Count(list))},type table [d=text,c=text]) ),
    fn = (tab)=> 
        Table.ReplaceValue( 
            tab, 
            0, 
            each [d], 
            (x,y,z) => Text.From( 
                List.Count( 
                    List.Select( 
                        List.Combine( 
                            List.Transform( 
                                tab[d] & tab[c], 
                                each Text.ToList(_) 
                            )
                        ), 
                    each _ = z ) 
                ) 
            ), 
            {"c"}
        ),
    gen = List.Generate(
        () => [t1 = source, t2 = Table.Buffer( fn(source) )],
        each [t1][c] <> [t2][c],
        each [t1 = [t2], t2 = Table.Buffer( fn( [t2] ) )],
        each [t2]
        ),
    out = List.Last( gen )
in
    out
Вот горшок пустой, он предмет простой...
 
В этом предложении цифра 0 встречается 1 раз, цифра 1 - 7 раз, цифра 2 - 3 раз, цифра 3 - 2 раз, цифра 4 - 1 раз, цифра 5 - 1 раз, цифра 6 - 1 раз, цифра 7 - 2 раз, цифра 8 - 1 раз, цифра 9 - 1 раз


Код
Sub ttt()
Dim i As Integer, J As Integer, s As Long
Dim A(9)
i = 9
Do While i >= 0
    s = 0
    J = 0
    Do While J <= 9
        s = s + Len(CStr(A(J))) - Len(Replace(CStr(A(J)), CStr(i), ""))
        J = J + 1
    Loop
    If A(i) <> s + 1 Then
        A(i) = s + 1
        i = 9
    Else
        i = i - 1
    End If
Loop

strRes = "В этом предложении цифра 0 встречается " & a(0) & " раз, "
For i = 1 To 8
strRes = strRes & "цифра " & i & " - " & a(i) & " раз, "
Next
strRes = strRes & "цифра " & 9 & " - " & a(9) & " раз"
Debug.Print strRes
End Sub
Изменено: БМВ - 16.02.2020 18:47:32
По вопросам из тем форума, личку не читаю.
 
Добрый день! Указанные решения не отвечают условию задачи #1. Фраза должна быть грамматически верной. Никто не разрешал самовольно добавлять букву (ы) "а".
Есть ли корректное решение? :)

Если не обращать внимание на грамматику. Подсказка.

Представим решение в виде массива A(0 to 9) натуральных чисел: A(0) - число упоминаний цифры 0, ..., A(9) - число упоминаний цифры 9.
Разобъем все решения на два класса.
1. Все элементы массива не более 9 (являются цифрами). Тогда общее число всех цифр  во фразе будет 10 (они уже есть в исходной фразе) + 10 (по одной цифре из массива). Значит, сумма всех элементов массива равна 20. Далее легко и без компьютера
2. Среди элементов массива есть хотя бы одно число, большее 9. Очевидно, что число, большее 9, может быть только одно и это - A(1).
Изменено: sokol92 - 16.02.2020 14:52:45
Владимир
 
Цитата
sokol92 написал:
Есть ли корректное решение?
1. По пункту 1 есть только одно решение (проверено моим кодом с учётом всего описанного Вами. Код БМВ,  тоже, наверное, это подтверждает, но он такой же как его формулы, а я временно не пью).
2. Почему "очевидно" что только 1 может быть больше 9? Может ли встречаться не 11 раз? Есть ли третье решение вообще?
3. Критикуя - предлагай.
Я не волшебник, я только учусь.
 
Симпатичная "олимпиадная" школьная задача. Не будем лишать участников форума удовольствия ею позаниматься...
Максим в #1 попросил сформулировать алгоритм. :)  
Владимир
 
Вот так отвлечешься, а тут уже на страницу. Пойду разбирать/тестировать коды :)
F1 творит чудеса
 
Цитата
sokol92 написал:
Симпатичная "олимпиадная" школьная задача.
- меня WADA дисквалифицирует :-) . Мой коТд не ищет все комбинации, довольствуется первой найденной.
Изменено: БМВ - 16.02.2020 18:58:18
По вопросам из тем форума, личку не читаю.
 
Скажу по секрету - задача вовсе не требует кода. :)  
Владимир
 
Зайдем с другой стороны.
Пусть S - общее количество цифр во фразе из #1, T - сумма вписанных значений (вместо троеточий). В начале S=10, T=0.
Когда мы всесто троеточия вписываем число n, то S увеличивается на число цифр числа n, а T увеличивается на n. Таким образом, наименьшее двузначное число 10 сокращает разрыв между T и S на 8. Понятно, что если число >=10 и есть, то оно одно. Таким образом, получается одно решение из пункта 2 #18 и еще одно (после короткого анализа) из пункта 1.

Опять же, если пренебречь грамматикой русского языка...
Владимир
 
А мне захотелось чуть причесать код Михаила (БМВ)
Ничего нового не добавил, только изменил циклы и ущел от текстовых строк
Код
Sub www()
    Dim i As Long, j As Long, s As Long, a(9) As Long
    For i = 9 To 0 Step -1
        s = 1
        For j = 0 To 9
            s = s - (a(j) Mod 10 = i) + (a(j) \ 10 = i) * (a(j) > 9)
        Next j
        If a(i) <> s Then
            a(i) = s
            i = 10 'не совсем красиво, но работает
        End If
    Next i
    Cells(1, 1).Resize(, 10) = a 'альтернативный вывод, для упрощения, можно оставить предыдущий вариант
End Sub
 
перебор через комбинаторику, который выдает оба варианта:
Код
Sub wwwCombin()
    Dim n As Long, i As Long, strRes As String
    Dim a() As Long, b(9) As Long
    
    Const m As Long = 9
    ReDim a(1 To m) As Long
    For n = 19 To 20
        For i = 1 To m: a(i) = i: Next i
        Do
            b(0) = a(1)
            For i = 1 To m - 1
                b(i) = a(i + 1) - a(i)
            Next i
            b(9) = n + 1 - a(m)
            If fCheck(b()) Then
                strRes = "В этом предложении "
                For i = 0 To 9
                    strRes = strRes & "цифра " & i & IIf(i = 0, " встречается ", " - ") & b(i) & " раз" & IIf(b(i) > 1 And b(i) < 5, "а", "") & IIf(i < 9, ", ", "")
                Next
                Debug.Print strRes
            End If
        Loop While NextCombin(a(), n, m)
    Next n
End Sub

Function fCheck(b() As Long) As Boolean 'проверка массива на соответствие
    Dim c(9) As Long, i As Long
    For i = 0 To 9
        c(b(i) Mod 10) = c(b(i) Mod 10) + 1
        If b(i) > 9 Then c(b(i) \ 10) = c(b(i) \ 10) + 1
    Next i
    For i = 0 To 9
        If c(i) + 1 <> b(i) Then Exit Function
    Next i
    fCheck = True
End Function

Function NextCombin(a() As Long, n As Long, m As Long) As Boolean 'следующее сочетание
    Dim i As Long, j As Long
    For i = m To 1 Step -1
        If a(i) < n - m + i Then
            a(i) = a(i) + 1
            For j = i + 1 To m
                a(j) = a(j - 1) + 1
            Next j
            NextCombin = True
            Exit For
        End If
    Next i
End Function
 
Цитата
MCH написал:
А мне захотелось чуть причесать код Михаила (БМВ)
Вернем строки и уберем один цикл
Код
Dim i As Integer, s As Long, a As String
a = "0, 0,1, 0,2, 0,3, 0,4, 0,5, 0,6, 0,7, 0,8, 0,9, 0"
For i = 9 To 0 Step -1
    s = Len(a) - Len(Replace(a, CStr(i), ""))
    If CLng(Mid(a, i * 5 + 3, 2)) <> s Then
        a = Left(a, i * 5 + 2) & Right(" " & s, 2) & Mid(a, i * 5 + 5)
        i = 10
    End If
Next

Вывод чуть изменится  :D

А так еще смешнее
Код
Dim i As Integer, s As Long, a As String
a = "В этом предложении цифра 0 встречается ... раз, цифра 1 - ... раз, цифра 2 - ... раз, цифра 3 - ... раз, цифра 4 - ... раз, цифра 5 - ... раз, цифра 6 - ... раз, цифра 7 - ... раз, цифра 8 - ... раз, цифра 9 - ... раз"
a = Replace(a, "...", " 0")
For i = 9 To 0 Step -1
    s = Len(a) - Len(Replace(a, CStr(i), ""))
    If CLng(Mid(a, i * 18 + 40, 2)) <> s Then
        a = Left(a, i * 18 + 39) & Right(" " & s, 2) & Mid(a, i * 18 + 42)
        i = 10
    End If
Next
Debug.Print Application.Trim(a)
Изменено: БМВ - 17.02.2020 20:50:16
По вопросам из тем форума, личку не читаю.
 
Код
Sub www()
    Dim i As Long, j As Long, s As Long, a(9)
    For i = 9 To 0 Step -1
        s = 1 + Len(Join(a)) - Len(Replace(Join(a), i, ""))
        If a(i) <> s Then a(i) = s: i = 10
    Next i
    Cells(1, 1).Resize(, 10) = a
End Sub

Работа со строками крайне не эффективна при длительных расчетах, сделано исключительно для сокращения кода, в реальных задачах так не целесообразно делать
Изменено: MCH - 18.02.2020 13:21:42
 
OFF
Цитата
Jack Famous написал 4мя днями ранее:
а я пока стесняюсь код писать, а то придёт МСН и всем ататушки сделает со своей комбинаторикой
наши дни:
Цитата
БМВ: Вернем строки и уберем один цикл
Цитата
MCH: Работа со строками крайне не эффективна при длительных расчетах, сделано исключительно для сокращения кода, в реальных задачах так не целесообразно делать
:D  8)
Изменено: Jack Famous - 18.02.2020 16:27:01
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
 
Цитата
MCH написал:
Работа со строками крайне не эффективна при длительных расчетах,
С этим даже пытаться спорить не стану. Делал тоже исключительно ради прикола, особенно последний вариант.
А вот появление в самом первом варианте обработки строк, было обусловлено тем, что если число не двузначное , то вариант #25 не подойдет.
По вопросам из тем форума, личку не читаю.
Страницы: 1
Наверх