Algorytm dzielenia liczb binarnych

Question

Cześć. Mam w podręczniku taki algorytm w pseudokodzie i nie potrafię zrozumieć kilka jego części:

1. reszta <- a[0...d-1]

Co właściwie robi ten fragment? Chodzi o to by dodać kolejne elementy z tablicy od podanych id? W sumie tak zrobiłem, ale nie przyniosło to oczekiwanych rezultatów.

 

2. if(reszta  < b)

Z założeń przedstawionych na poprzedniej stronie reszta i b to stringi więc jak ma to właściwie działać? Jak interpretować ten fragment. Mimo wszystko spróbowałem napisać to zgodnie z wytycznymi książki, a później dodatkowo  dodać tam funkcję stoi jednak nie wiem czy o to chodziło:

Dodaj - Algorytm dodawania 2 liczb

Przeciwna - Zamienia liczbę na przeciwną w kodzie U2

Odejmij - Zwraca różnicę 2 podanych liczb

 

#include <iostream>
#include <string>
using namespace std;

string Dodaj(string a, string b)
{
    int przn = 0;
    string c;


    while(a.size() < b.size())
    {
        a = '0' + a;
    }

    while(b.size() < a.size())
    {
        b = '0' + b;
    }

    for(int i = a.size() -1; i >= 0; i--)
    {
       int suma = przn + a[i]-'0' + b[i]-'0';
       if(suma % 2 == 1)
       {
           c = '1' + c;
       }
       else
       {
           c = '0' + c;
       }

       przn /= 2;
    }

    if(przn == 1)
    {
        c = '1' + c;
    }

    return c;
}

string Przeciwna(string s)
{
    int i = 0;
    for(i = 0; i < 8; i++)
    {
        if(s[i] == '0')
        {
            s[i] = '1';
        }
        else
        {
            s[i] = '0';
        }
    }

    s = '0' + s;
    i = 8;

    while(s[i] == '1')
    {
        s[i] = '0';
        i--;
    }
    s[i] = '1';
    return s.substr(1,8);
}

string Odejmij(string a, string b)
{
    return Dodaj(a, Przeciwna(b));
}

int main()
{

    int ilorazc = 1, d;
    string a, b, reszta;
    cin >> a >> b;

    d = b.size();

    for(int i = 0; i < d; i++)
    {
    reszta += a[i];
    }

    if(stoi(reszta) < stoi(b))
    {
        reszta += a[d];
        d++;
    }

    reszta = Odejmij(reszta, b);

    for(int i = d; i < a.size(); i++)
    {
        reszta += a[i];
        if(stoi(reszta) < stoi(b))
        {
            ilorazc += '0';
        }
        else
        {
            ilorazc += '1';
            reszta = Odejmij(reszta,b);
        }
    }


    cout<< reszta;

    return 0;


}

 

Answer 1

1.  Nie, masz w komentarzu do tej linii: “zapisanie w zmiennej reszta d pierwszych znaków z napisu a”.
2.  Potrzebna jest osobna funkcja porównująca, ponieważ liczba może się nie zmieścić w granicach typu int.

W funkcji Dodaj masz błąd. Nie powinno być raczej:

przn = suma / 2;

Reszty nie sprawdzałem.

Algorytm opiera się o pisemne dzielenie, tylko na liczbach binarnych. I wydaje się również błędny, ponieważ na początku arbitralnie przypisuje do wyniku pierwszą 1.

Comments

zapisanie w zmiennej reszta d pierwszych znaków z napisu a

Nie mam pojęcia jak zrozumieć ten fragment. Czyli, że do zmiennej reszta przypisujemy kolejne d znaków ze zmiennej a? Bo brzmi to tak jak pętla, którą zastosowałem do rozwiązania tego problemu (Linie 85-88). Czy mógłbyś pokazać jak to przedstawić w c++?

 

Co do tej 1 na początku to chyba wynika to z założenia, że a > b zawsze:

 

 

---

Ok, czyli jest to za­łoże­nie, że a > b.

Pod ram­ką jest opi­sa­ne dok­ła­d­nie, co ro­bi ta li­nia. Tyl­ko de­fi­niujesz to ja­ko do­da­wa­nie (su­mo­wa­nie), a jest to scala­nie czyli su­bstr.

Twoja fun­kcja Prze­ci­w­na nie ma szans dzia­łać po­pra­w­nie, po­nie­waż nie zna dłu­go­ś­ci zmien­nej reszta, po­d­czas gdy mu­si do­dać je­dyn­ki na po­czą­t­ku do dłu­go­ś­ci tej zmien­nej. Może le­piej za­im­ple­men­to­wać fun­kcję Odej­mij wprost? Na przykład:

#include <iostream>
#include <string>
using namespace std;
 
string Dodaj(string a, string b)
{
    int przn = 0;
    string c;
 
 
    while(a.size() < b.size())
    {
        a = '0' + a;
    }
 
    while(b.size() < a.size())
    {
        b = '0' + b;
    }
 
    for(int i = a.size() -1; i >= 0; i--)
    {
       int suma = przn + a[i]-'0' + b[i]-'0';
       if(suma % 2 == 1)
       {
           c = '1' + c;
       }
       else
       {
           c = '0' + c;
       }
 
       przn = suma / 2;
    }
 
    if(przn == 1)
    {
        c = '1' + c;
    }
 
    return c;
}
 
string Odejmij(string a, string b)
{
    int przn = 0;
    string c;
 
 
    while(a.size() < b.size())
    {
        a = '0' + a;
    }
 
    for(int i = 0; i < b.size(); i++)
    {
        if(b[i] == '0')
        {
            b[i] = '1';
        }
        else
        {
            b[i] = '0';
        }
    }
    b = Dodaj( b, "1" );
    while(b.size() < a.size())
    {
        b = '1' + b;
    }
 
    for(int i = a.size() -1; i >= 0; i--)
    {
       int suma = przn + a[i]-'0' + b[i]-'0';
       if(suma % 2 == 1)
       {
           c = '1' + c;
       }
       else
       {
           c = '0' + c;
       }
 
       przn = suma / 2;
    }
 
    return c;
}
 
int main()
{
 
    string ilorazc = "1";
    int d;
    string a, b, reszta;
    cin >> a >> b;
 
    d = b.size();
 
    reszta = a.substr(0, d);

    if(stoi(reszta,0,2) < stoi(b,0,2))
    {
        reszta += a[d];
        d++;
    }

    reszta = Odejmij(reszta, b);

    for(int i = d; i < a.size(); i++)
    {
        reszta += a[i];
        if(stoi(reszta,0,2) < stoi(b,0,2))
        {
            ilorazc += '0';
        }
        else
        {
            ilorazc += '1';
            reszta = Odejmij(reszta,b);
        }
    }
 
 
    cout << ilorazc << endl;
 
    return 0;
 
 
}

Pozostaje napisanie funkcji porównującej zamiast stoi.

---

Teraz wszystko ma więcej sensu. Nie sądziłem że z tym pierwszym problemem chodzi o użycie tam substr. Przeanalizuję poprzednie algorytmy i raczej już sobie poradzę. Dziękuję ślicznie