Witam, mam takie zadanko:
Wczytac z wejscia ciąg zer i jedynek o
dlugosci nie wiekszej niz 100 znakow, ktory traktowany
jest jako reprezentacja liczby naturalnej w systemie
dwojkowym, a nastepnie wypisac te liczbe w systemie
dziesietnym. Pamietac o kontroli poprawnosci danych.
I teraz mam problem, jak to zrobić bez użycia tablicy? Z tablicą to easy ale niestety dostaliśmy rozkaz na ćwiczeniach żeby bez...
a jaki to problem, że bez tablicy?
char liczba;
int i=0,s=0;
for(i=0;i<100;i++)
{
scanf("%c",&liczba);
if(liczba=='1')
s+=pow(2,i);
}
no.. chyba ze jest inna kolejnosc bitow - wtedy
while( scanf("%c",&liczba) && i<100)
{
s*=2;
if(liczba=='1')
s++;
i++;
}
mądra się znalazła. Odpowiedz sobie na proste pytanie ile bitów ma int, a zrozumiesz czemu to zadanie nie jest proste (nie mówiąc już o tym, że twoja implementacja jest naiwna).Bez tablic nie da rady i potrzebujesz co najmniej dwie tablice: jedną do liczenia kolejnych potęg 2 w systemie 10 a drugą do dodawania tych potęg w zależności od wartości bitu.
Dla prostoty załóż że w jednym bajcie przechowujesz jedną cyfrę (jak jesteś bardziej kumaty możesz przechowywać 2 cyfry, coś ala system setkowy).
właśnie ;] próbowałem najpierw liczyć cyferki getcharem żeby określić liczbę potęg ale potem jeżeli mam liczbę potęg to znowu nie mam liczby...
potrafisz zaimplementować możenie i dodawanie pisemne?
Jeśli tak to napisanie podnoszenia do kwadrat z poprzedniego wyniku kwadratu 2 itd nie powinno być dla ciebie trudne. A potem dodawać lub nie te wartości zależnie od wartości bitu.
ale z tablicami (nawet jedną) to ja to umiem napisać. tylko nie wiem jak bez, a skoro nam kazała bez, to widocznie się da jakoś :P
sam jestem ciekawy niby jak by to miało być bez tablic?
Przecież 2^100 = 1267650600228229401496703205376, czyli ustawienie lub nie nie najstarszego bitu ma wpływ na każdą cyfrę w systemie dziesiętnym. Czyli trzeba przynajmniej stabilizować daną wejściową, żeby cokolwiek można było zrobić.
Jeśli miałby zgadywać to pewnie trzeba wykorzystać algorytm liczenia (a^2)%c, gdzie c=10 lub dla optymalizacji c = 100000000 (największa potęga 10, która "wejdzie" do 32 bitowej liczby). Czyli do pełnego zapisu binarnego tej liczby potrzebujesz 4 standardowych int'ów.
// albo jednego 128bitowego inta, a procki x86 128bit sa dopiero projektowane [mf]
Czy myślałeś o zastosowaniu chińskiego twierdzenia o resztach?
http://pl.wikipedia.org/wiki/Chińskie_twierdzenie_o_resztach
Chociaż tutaj, też trzeba coś w pamięci przechowywać. Niekoniecznie w tablicy i przy liczbach 100 bitowych może być łatwiej zapisać je w czterech int...
A jak wyglada sprawa z nieznaczacymi zerami? Dostajesz je na wejsciu czy nie? Bo jesli nie, to bez tablicowania danych (chyba) nie da rady
szczerze mówiąc darowałem sobie to. jeżeli pokaże nam rozwiązanie to na pewno wrzucę tutaj.