- 1
- 2
-
pan.Tunio
witam wszystkich
otoz mam taki problem:
mam dwie liczby ktore zapisane są w formie dwóch tablic (każda cyfra liczby, jest oddzielną komórką w tablicy -> takich liczb mam dwie). no i te liczby muszę pomnożyć.
więc najbardziej oczywistym i pierwszym tropem jest mnożenie pisemne (lub jak ktoś woli pod kreską).
no i tutaj zaczynają sie schody.... przynajmniej dla mnie.
bo napewno potrzeba dwóch pętli, jednak która leci po cyfrach jednej liczby, a druga która leci po cyfrach drugiej liczby. to jest ok. jednak teraz tak:
po każdym 'obroceniu sie' petli pierwszej ktora mnozy kazda cyfre pierwszej liczby, przez jedna cyfre drugiej. potem musimy wziac druga cyfre drugiej i zrobic dokladnie to samo - jednak wynik trzeba przesunac o jeden gdyz przeciez mnozymy przez dziesiatki. i tak jedziemy przez wszystkie cyfry drugiej liczby, odpowiednio dodajac zera do wyniku na koniec (gdyz jedziemy po jednosciach, potem dziesiatkach, setkach, tysiacach itp).
czy ma ktos pomysl jak to zrobic?
siedze nad tym juz dosc dlugo jednak na nic konstruktywnego nie wpadlem.
bede wdzieczny za kazda pomoc
pozdrowki -
Kuba
//--------
//tab1, tab2 - dwie tablice
int liczba1 = 0;
int liczba2 = 0;
for(int i = 0; i < tab1.length; i++)
liczba1 = liczba1*10 + i;
for(int i = 0; i < tab2.length; i++)
liczba2 = liczba2*10 + i;
int iloczyn = liczba1 * liczba2;
//--------
tak chyba naprosciej jest -
Brut[all]
> liczba1 = liczba1*10 + i;
> liczba2 = liczba2*10 + i;
Nie i, tylko tab1.
A jeśli bardzo Cię interesuje to mnożenie pod kreską, to..
int suma = 0;
for(int i = 0; i < tab1.length; i++)
for(int j = 0; j < tab2.length; i++)
suma += tab1 * tab2[j] * 10 ^ (i + j);
I tyle.
Prawda, że proste? :)
Tam oczywiście ma być podnoszenie do potęgi, ale nie jestem programistą Java, więc nie wiem, czy to tak, czy może jakiś pow() jest. -
Brut[all]
Aha.
No i algorytm Kuby zakłada, że cyfry w tablicach są zapisane od najstarszej, do najmłodszej - u mnie jest odwrotnie.
Ale to kwestia zapisu. -
-
Kuba
>Nie i, tylko tab1.
wybacz, dopiero co wstalem, po 14 godzinach snu ledwo co widze na oczy; ) -
Anonim
ooo pisalem kiedys cos takiego na pierwszym semestrze na WDP tyle że w paszczaku
do sciagniecia (chyba tam jest) http://www.ii.uj.edu.pl/~kokoszka -
pan.Tunio
suma += tab1 * tab2[j] * 10 ^ (i + j);
ciekawi mnie ta linijka brut[all]...
bo przy pierwszym obrocie petli, czyli gdy cyfry liczby pierwszej mnozysz po kolei przez ostatnia cyfre (cyfre jednosci) liczby drugiej - > wtedy powinno byc wszystko pomnozone przez 10^0 czyli 1, bo przy jednościach nie ma tego przesunięcia.
mam racje czy może coś źle gadam? -
Brut[all]
-
Brut[all]
Ahh.. myślałem, że Ci chodzi tylko i wyłącznie o pierwsze wystapienie tej linijki, a Tobie chodzi o przejście wszystkich j, czyli jeden z liczb, przy mnożeniu przez cały czas cyfrą jedności pierwszej?
Jeśli tak, to masz rację, tylko że zauważ, że w tablicach są tylko cyfry, więc jeśli mnożysz.. echh.. może przykład:
38 * 56
Najpierw mnożysz 8 * 6 * 1, więc jest wszystko, Twoim zdaniem, ok.
Potem mnożysz 6 * 50 * 10 i tak dziesiątka Ci nie pasuje, bo przesuwa, choć nie powinna.
Tak, tylko że Ty wcale nie mnożysz 6 * 50, a 6 * 5, prawda? :)
To Ci powinno rozjaśnić sprawę :) -
pan.Tunio
ok na przykladzie twoim:
38 * 56
robimy sobie tablice wynikową o dlugosci tab1.length+tab2.length wiec 4.
potem lecimy z mnozeniem
6*8 - no i razy jeden
potem
6*3 - znowu razy jeden
potem
5*8 - i tutaj juz razy 10
potem
5*3 - znowu razy 10:)
generalnie algorytm w miare rozumiem, jednak po prostu mam ogromna trudnosc z napisaniem tego w javie -
Anonim
a tak ogolnie to zalozyliscie sobie ze wynik dzialania zmiesci sie w zmiennej typu int :] a to nie koniecznie musi byc prawda -
Brut[all]
Ahh.. po prostu nigdzie nie napisałeś, że wynik ma być w takiej samej postaci, jak dane wejściowe :)
I nie tylko ja założyłem inaczej :)
W takim razie:
int k;
/* Tutaj deklaracja tablicy wynik o rozmiarze tab1.length + tab2.length - nie mam pojęcia, jak to się robi w Javie :)
Jeśli Java wymaga zerowania zmiennych, to trzeba i to zrobić dla wszystkich elementów tablicy wynik */
for(int i = 0; i < tab1.length; i++)
for(int j = 0; j < tab2.length; i++)
{
k = tab1 * tab2[j];
wynik[i + j] += k % 10;
wynik[i + j + 1] += floor(k/ 10);
}
Tu znów zastosowałem "ogólny" zapis - floor(), czyli zaokrąglanie do całkowitej w dół oraz k % 10, czyli reszta z dzielenia. -
pan.Tunio
mając zmienną typu int nie trzeba robić floor, bo domyślnie dzieli się calkowicie uzywajac '/'
jednak zdaje mi sie ze algorytm twoj nadal jest troche nie poprawny
wynik[i + j] += k % 10;
przykladowo ta linijka, bedzie powodowala skoki juz po przejsciu do dziesiatek w liczbie gornej czego nie chcemy, chcemy skakac dopiero gdy na dolnej licznie zaczniemy mnozyc dziesiatkami
znow: moge sie mylic, ale zdaje mi sie ze dosc logicznie mysle -
Anonim
ten algorytm tez sie wywali :)
może dojść do sytuacji że w tablicy wynikowej w niektorych polach nie będzie cyfr tylko kilku cyfrowe liczby :) -
Anonim
w gruncie rzeczy mozna by na koncu zrobic porzadkowanie tego wszystkiego ale to nie bylo by bazpieczne bo nie wiadomo czy w to co by wyszlo zmiesci sie w bajcie -
Brut[all]
> ten algorytm tez sie wywali :)
>może dojść do sytuacji że w tablicy wynikowej w
> niektorych polach nie będzie cyfr tylko kilku
> cyfrowe liczby :)
Ahhh.. wiem, wiem, na początku miałem zrobić inaczej, ale przed samym napisaniem postu wpadłem na "genialny" sposób przyśpieszenia tego..
int len = tab1.length + tab2.length;
wynik = array itd.
for(i = 0; i < tab1.length; i++)
for(j = 0; j < tab2.length; j++)
wynik[i + j] += tab1 * tab2[j];
for(i = 0; i < len - 1; i++)
{
wynik[i + 1] += wynik/ 10;
wynik %= 10;
}
I tak mam wrażenie, że coś gdzieś pogryzłem :/ -
Brut[all]
> przykladowo ta linijka, bedzie powodowala skoki
> juz po przejsciu do dziesiatek w liczbie gornej
> czego nie chcemy, chcemy skakac dopiero gdy na
> dolnej licznie zaczniemy mnozyc dziesiatkami
>znow: moge sie mylic, ale zdaje mi sie ze dosc
> logicznie mysle
A jeśli mnożysz ten przykład 38 * 56, najpierw robisz 6 * 8, wstawiasz do jedności, dochodzisz do 6 * 3 i to też wstawiasz w "kratkę" od jedności?
Bo tak by wynikało z tego, co mówisz. -
Anonim
nie chce być upierdliwy (choć wiem że jestem :D), ale to dalej nie zadziala moze dojsc do sytuacji gdzie w np wynik[21] bedzie liczba powiedzmy 211 (a moze i to nawet bedzie zle jak sie licznik pare razy przekreci) i teraz bedziesz to wszystko przesuwal az na sam koniec tablicy (licznik znowu sie pewnie pare razy przekreci) i w ostatnim polu zostanie nie cyfra tylko liczba
wszystko by bylo ok ale bajt to tylko 256 ...
ja to widze tak:
a pierwsza tablica b druga tablica c trzecia tablica
a - wynik mnozenia ostatniej cyfry przez liczbe
b - wynik mnozenia przedostatniej przez liczbe
c - wynik dodawania a + b
pozniej sobie zamien tablice a z c
b - wynik mnozenia trzeciej od konca przez liczbe
c- wynik dodawania a + b
zamiana a z c
b - wynik mnozenia 4 od konca przez liczbe i tak dalej
oczywiscie nie wnikam w szczegoly dodawania dwoch liczb z tablicy, czy tez mnozenia liczby przez liczbe jedno cyfrowa, ale to mozna zrobic dokladnie jak przy działaniach pod kreske
-
Anonim
-
Anonim
acha no w sumie w pierwszym poscie nic nie bylo o typie tej tablicy, ale dowolnie duzych typow mozna znalezc tak duze liczby ze to co wczesniej bylo podawane sie wywali
- 1
- 2
- Przeglądaj grona w kategorii Internet i Komputery
- Przeglądaj grona w okolicy Warszawa
- Załóż własne grono tematyczne
- Zostań moderatorem
Podobne Tematy
|
|
Wszystko co związane z programowaniem w Java (J2EE, JSP, JDBC, itd) test
Fotki
Miejsca grona (1)
-
Kino Luna ul. Marszałkowska, Warszawa
www.kinoluna.pl kino.luna@maxfilm.com.pl 22 621 78 28
- Dodaj miejsce