Zabawe z programowaniem zacząłem niedawno, dlatego moje umiejętności są ograniczone, ale ucze się na bieżąco nowych rzeczy w języku C. Moim ostatnim problemem jest znalezienie okresu ulamka, mówiąc dokładniej - podaje dwie liczby naturalne p i q i jeśli ułamek jest skończony to go wypisuje jeśli nie to mam podać jego rozwinięcie okresowe. Niestety po dłuższym namyśle niestety nie potrafie znaleźć żadnego prostego algorytmu na znalezienie okresu. Macie jakiś pomysł na to?
Wyszukiwanie okresowości
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: XML Hills
1
Robisz to tak jak na matematyce w przedszkolu - dzielisz pisemnie, aż ci się reszty zaczną powtarzać.
- Rejestracja: dni
- Ostatnio: dni
- Postów: 20
0
myślałem nad tym ale nie znam metody która mogłbym to zapisac - bo okres moze zaczynac sie juz od pierwszej liczby po przecinku (mnp. 1/3) ale może też zaczynac sie dopiero od 4 (dla np. 1/7000). Zasugeruj jakim narzedziem sprawdzania mam sie posluzyc.(?)
- Rejestracja: dni
- Ostatnio: dni
1
To jest potwornie skomplikowany algorytm składający się z dwóch pętli oraz jednego if'a:
#include <string>
#include <iostream>
using namespace std;
int main()
{
string str="1.428571428571";
size_t len=str.length(),max=len-1,min=len>>1;
for(size_t p=max-1;p>=min;--p)
{
bool same=true;
size_t i,k;
for(i=max,k=p;(i>p)&&(same);--i,--k) same=(str[i]==str[k]);
if(same)
{
cout<<str.substr(0,p+1)<<"("<<str.substr(p+1)<<")"<<endl;
break;
}
}
return 0;
}
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Space: the final frontier
- Postów: 26433
0
Oczywiście rozwiazanie @_13th_Dragon trzeba trochę ztuningować, bo musisz kolejne elementy sobie wyliczać i dokładać do stringa z liczbą ;)
- Rejestracja: dni
- Ostatnio: dni
- Postów: 20
0
Moj pomysl jest taki -tablice sa wykonane dobrze, jednak przy wyszukiwaniu dlugosci okresu i wypisywaniu go zaczyna sie coś sypać i niestety nie potrafie stwierdzić co :( jakieś sugestie?
#include <stdio.h>
int main(void)
{
int tablica[100] = {0},i=0;
int table[100]= {0};
int a,b,c,d;
int j,k,m,x,e, found;
printf ("Podaj liczbe a\n");
scanf ("%d", &a);
printf ("Podaj liczbe b\n");
scanf ("%d", &b);
c=a%b;
e=a/b;
x=0;
table[0]=e;
tablica [0]=c;
printf ("tablica[%d]=%d\n", x, tablica[x]);
for(i=1 ; i<100 ; i++)
{
d=(tablica[i-1])*10;
c = d % b;
e= d/b;
table[i]=e;
tablica[i]=c;
printf ("tablica[%d]=%d\n", i, tablica[i]);
}
found=0;
for (k=1; k<100; k++) //ustawienie dlugosci okresu
{
printf ("co bierzesz?\n %d", k);
for (j=1; j<100; j++) //szuaknie okresu
{
if (table[j]=table[j+k]) //znalezienie okresu
{
found=1;
printf ("jaka wartosc found? %d\n", found );
for (m=j; m<(j+k); m++) //wypisanie liczb w okresie
{
printf ("Nr w tablicy %d wartosc %d\n",m, table [m]);
}
}
if (found==1)
{
br1eak;
}
}
if (found==1)
{
break;
}
}
return 0;
}
- Rejestracja: dni
- Ostatnio: dni
0
Wydaje mi się że takie rozwiązanie jest prostsze niż kod dragona (a na pewno niż to w poprzdnim poście, które nie wygląda na poprawne):
// deklaracje i wczytanie zmiennych - p i q jak w zadaniu.
int p, q;
std::cin >> p >> q;
std::vector<int> remainders(q, -1);
// samo szukanie kolejnych cyfr w postaci dziesiętnej
std::string frac;
for (int i = 0; remainders[p % q] < 0; i++) {
remainders[p % q] = i;
frac += '0' + (p * 10 / q) % 10;
p = (p * 10) % q;
}
// wypisanie wyniku
int init = remainders[p % q];
std::cout << (p / q) << "." << frac.substr(0, init) << "(" << frac.substr(init) << ")\n";
Jak to się zachowuje:
msm@andromeda ~ $ ./frac 1 7
0.(142857)
msm@andromeda ~ $ ./frac 1 13
0.(076923)
msm@andromeda ~ $ ./frac 7 12
0.58(3)
msm@andromeda ~ $ ./frac 1 4
0.25(0)
Ostatnie to prawdopodobnie nie to czego byś oczekiwał, ale na pewien sposób logiczne (zero powtarza się bez końca ;) ) - żeby poprawić wystarczy oczywiście rozważyć to jako specjalny przypadek.