Liczba, której iloczyn jest równy N ZosiaZamoyska: Szukam czegoś co można by nazwać wzorem... Zadanie brzmi tak: "Adam wymyślił nową zagadkę. Polega ona na znalezieniu najmniejszej liczby , której iloczyn cyfr jest równy N". Liczba 1 ≤ N ≤ 10⁹ ... Pomoże ktoś jakiś pomysł znaleźć? (np. dla N=18, jest to liczba 29, bo 2*9=18)

Draghan: Witaj, Zosiu To jest zadanie z informatyki, tak? Nie mam pojęcia, jak można by to było rozwiązać matematycznie, ale np. w formie programu to jest banalne do wykonania Oczywiście, jeśli chodzi o zadania z olimpiad, to raczej nie można za mocno podpowiadać?

ZosiaZamoyska: Tak, to jest z informatyki Ale to nie z olimpiady, olimpiada skończyła się ( I etap ) 9 stycznia, a II etap był 22 marca, a do III nie przeszłam Jeśli chcesz pomóc z pomysłem na program, to zajrzyj tu: http://forum.4programmers.net/C_i_C++/232230-latwiejszy_sposob_na_rozwiazanie_zadania?p=1026241#id1026241 Dzięki, jeśli pomożesz...

głupmen: pewnie, że można to za pomocą wzoru obliczyć, ale tak jak kolega wyżej wspomniał − wynik musi analizować program komputerowy, gdyż nie jest to jeden konkretny a kilkanaście+

Draghan: C++

głupmen: @Zosia mogę to za ciebie napisać, ale jest to banalna sprawa i boję się, że przestałaś na tym etapie myśleć, spróbuj rozrysować to na bloczkach, będzie ci łatwiej.

ZosiaZamoyska: No a jakże

ZosiaZamoyska: Nie chodzi o to, by ktoś za mnie napisał, bo pisać to ja umiem, ale o sam pomysł, szybszy niż mój

ZosiaZamoyska: Chociaż nie do końca rozumiem, co masz na myśli pod słowem "bloczki"...

głupmen: co masz na myśli: szybszy?

głupmen: @Zosia schemat blokowy ułatwia wyznaczenie opisu matematycznego, który może usprawnić wdrożenia owego problemu do programu

Trivial: Oczywiście można tutaj użyć schematu blokowego, ale nie mam zielonego pojęcia w jaki sposób miałby ułatwić "wyznaczenie opisu matematycznego". Schematy blokowe są strasznie niskopoziomowe i zorientowane na szczegóły, co przy projektowaniu jest zazwyczaj przeszkodą. Co do samego problemu... Rozwiązanie jest dość proste. Aby zadanie dało się rozwiązać musi zachodzić: N = 2^c₂ * 3^c₃ * 4^c₄ * ... * 9^c₉ gdzie liczby c_k są naturalne (z zerem) oraz przynajmniej jedno c_k ≠ 0. Powiedzmy, że liczbę N da się rozłożyć w opisany wyżej sposób. Zauważmy, że najmniejszą liczbę X spełniającą warunki zadania otrzymamy dla: 1) Minimalnej ilości cyfr liczby X (czyli minimalnej sumy c₂ + c₃ + ... + c₉). 2) Takiego ustawienia cyfr liczby X, aby najmniejsze były "na początku", a największe "na końcu". Powyższe warunki narzucają unikalny rozkład, który można obliczyć algorytmem zachłannym. Przebieg: 1. Każdemu c_k przypisujemy na początku 0. 2. Dla k = 9, 8, 7, ..., 2: 3. Sprawdzamy czy N jest podzielne przez k. 4. Jeśli tak to c_k ← c_k + 1, dzielimy N przez k oraz wracamy do kroku (3). 5. Jeśli nie to przechodzimy do następnego k. Poszukiwaną liczbę X tworzą kolejno: X = c₂ dwójek, c₃ trójek, ..., c₈ ósemek, c₉ dziewiątek. Wprawny czytelnik zauważy, że dla N = 1 powyższy rozkład nie istnieje, ale wtedy po prostu X = 1. Dodatkowo to, czy liczbę N da się rozłożyć można wykryć w zależności od wartości N po wykonaniu algorytmu. Jeśli końcowe N ≠ 1, to rozwiązanie nie istnieje.

Trivial: I rozwiązanie dla dowolnego N: http://ideone.com/et9Kaj

Draghan: Podziwiam Zastanawia mnie, co to za język, ten Haskell? Aż chyba sobie o nim poczytam Trivial, jakie są jego główne zastosowania?

Trivial: To język badawczy ogólnego przeznaczenia, ale ostatnio zyskuje popularność także poza researchem. Ma kilka osobliwych cech, które skutecznie rozsadzają głowy tradycyjnych programistów imperatywnych. Między innymi: (1) Nie pozwala na żadne mutacje "zmiennych". (2) Skoro mutacje nie są możliwe, to nie ma pętli. (3) IO realizowane jest poprzez użycie monad importowanych wprost z teorii kategorii. (4) Nic nie jest obliczane dopóki nie jest potrzebne (tzw. lazy evaluation). (5) Wszystkie funkcje są tak naprawdę funkcjami jednej zmiennej co umożliwia bardzo proste wykorzystanie tzw. partial application. (6) Klasy typów (ang. type classes) umożliwiają zupełne inne podejście do polimorfizmu, które w wielu zastosowaniach sprawdza się dużo lepiej niż podejście tradycyjne. (7) Przerobienie programu, który wykonuje się na jednym procesorze na taki, który działa równolegle na wszystkich rdzeniach jest często trywialnie proste (np. dodanie jednej linijki). I wiele innych... Poza tym na zawsze zmienia sposób myślenia o projektowaniu funkcjonalności w innych językach oraz powoduje, że co rusz brakuje nam rozmaitych funkcjonalności w tych innych językach.

Draghan: "Poza tym na zawsze zmienia sposób myślenia o projektowaniu funkcjonalności w innych językach oraz powoduje, że co rusz brakuje nam rozmaitych funkcjonalności w tych innych językach." To brzmi najbardziej intrygująco No i jeszcze brak pętli... No i wszystko inne Mamo moja... Twój program ma tylko 15 linijek! (i połowy z tego nie łapię ) W starym, dobrym C++ to wymagałoby więcej kodu. Dziękuję za opis, coraz bardziej mnie to ciekawi... Miłego dnia

Trivial: To zadanko w C++ jeszcze nie jest takie straszne. http://ideone.com/bp7vCk

Draghan: Nie twierdzę, że straszne, tylko że ciężko byłoby to zawrzeć w 15 linijkach Tak ładnie to rozpisałeś, że nawet dzieci nie powinny mieć problemu z napisaniem tego Oczywiście, jak się ktoś uprze, to wszystko napisze w jednej No, w trzech, bo mamy dwie dyrektywy O jak ładnie Moje nieszczęsne duble zniknęły Dobre wróżki czuwają Jeszcze raz życzę miłego dnia