[Algorytmy][C++] Wielokrotność z zerami i jedynkami

freeszpak · Post autor: **freeszpak** » 9 kwie 2016, o 19:51

Dla każdej liczby naturalnej \(\displaystyle{ n}\) istnieje takie \(\displaystyle{ k}\), że \(\displaystyle{ n \cdot k}\) ma w zapisie dziesiętnym same zera i jedynki. Napisz funkcję, która dla zadanego \(\displaystyle{ n}\) obliczy \(\displaystyle{ k}\).

W jaki sposób komputer ma sprawdzić czy liczba składa się z samych zer i jedynek? Czy w ogole istnieje jakis algorytm ktory moglby wyznaczać wartość k? Bo nie mogę takiego wymyślić...

dec1 · Post autor: **dec1** » 9 kwie 2016, o 20:02

Czy \(\displaystyle{ k}\) też musi być naturalne? No bo jeśli nie to \(\displaystyle{ k=\frac{10}{n}}\) będzie spełniało warunki zadania.

freeszpak · Post autor: **freeszpak** » 9 kwie 2016, o 20:05

całkiem dobre pytanie nie ma o tym nic w poleceniu wiec moze chyba tak byc jak napisałes

dec1 · Post autor: **dec1** » 9 kwie 2016, o 20:10

Pewnie autorowi chodziło o coś innego no ale jak takie nieścisłości są...

Medea 2 · Post autor: **Medea 2** » 9 kwie 2016, o 23:11

Gotowiec, ale niech Ci będzie:

Kod: Zaznacz cały

https://oeis.org/A079339

.

freeszpak · Post autor: **freeszpak** » 10 kwie 2016, o 17:50

Kliknąłem "pomógł" za tego gotowca ale ile tam się naszukałem to nic nie znalazłem

Tzn coś tam jest ale mocno skomplikowane i chyba nie jest to napisane w c++?
Mam takie coś i działa, może jak ktoś kiedyś będzie szukał to mu się przyda

Kod: Zaznacz cały

#include <iostream>
#include <cassert>
#include <sstream>

using namespace std;

bool czyzerajedynki(int x)
{
    ostringstream strumien;
    strumien << x;                          //zamiena int na string
    string napis = strumien.str();

    for(int y = 0; y < napis.length(); y++)
    {
        if(napis[y]!='0' && napis[y]!='1')
            return 0;
    }
    return 1;
}

int zerojeden(int n)
{
    int k = 1;

    while(czyzerajedynki(n*k)!=1)
    {
        k++;

        if(n*k>214748364) //rozmiar int
        {
            return -1;
        }
    }

    return k;
}

int main()

{
    int p;
    cin >> p;
   cout << zerojeden(p);

    return 0;
}

Medea 2 · Post autor: **Medea 2** » 11 kwie 2016, o 01:15

Trochę schludniej

Kod: Zaznacz cały

https://ideone.com/6H24L2

freeszpak · Post autor: **freeszpak** » 11 kwie 2016, o 02:01

Rzeczywiście, dobre.

a4karo · Post autor: **a4karo** » 11 kwie 2016, o 07:59

Może to i dobre, ale liczby, na których będziesz pracował mogą miec po kilka tysięcy cyfr i żaden long long long int Ci tego nie załatwi.

W zadanie wcale nie chodzi i wypisywanie cyfr, tylko o metodę wyznaczenia takich liczb.

Wsk: popatrz na resztyy z dzielenia przez \(\displaystyle{ n}\) liczb \(\displaystyle{ 1, 11, 111, 1111, ....}\) aż do liczby, która ma \(\displaystyle{ n}\) cyfr.