Ciąg cyfr.

0

Witam!

Panowie, jest w stanie ktoś z Was rozwiązać to zadanie: Klik! ?
Siedzę nad tym już drugi dzień, zrobiłem: podanie liczby, która określa ile liczb możemy wprowadzić, obliczanie potęgi liczby 10 za pomocą pow z math.h, lecz tu istnieje problem... do tablicy zapisywane są np. tab[0] = 1, tab[1] = 10, tab[2] = 100, a powinno być tab[0] = 1, tab[1] = 1, tab[2] = 0 itd.
Nie wiem jak to do końca rozwiązać.

Pozdrawiam!

0

Hm a może zamiast do tablicy do string-a z nimi? Starczy skonwertować, a z tego co widzę nie ma różnicy czy będziesz miał te zera i jedynki jako cyfry czy też znaki. Swoją drogą zauważ że po każdej jedynce występuje o jedno zero więcej niż po poprzedniej, więc moim zdaniem można policzyć gdzie będzie następna jedynka i na tej podstawie ustalić co wyświetlić bez pamiętania samego ciągu. Weźmy np przykładowy ciąg, jedynki mamy w 0,1,3,6,10, różnica między 10 i 6 wynosi 4, zatem następna będzie na 10 + (4 + 1 zer) = 15 pozycji. Starczy zapamiętywać gdzie jedynki, i liczyć sobie do momentu gdy osiągniesz/przekroczysz żądaną liczbę (pamiętanie po to że po niej może pojawić się mniejsza, wtedy tylko szukamy po tabeli zamiast liczyć od nowa)

0

Ale po co ci w tym zadaniu jakiekolwiek potęgi?

0

Muszą być potęgi bo jest napisane w zadaniu, że nieskończony ciąg, nie można na sztywno do tablicy przypisać wartości.

0

Ale przecież tworzysz tablicę (booli chociażby) o 65536 elementach i wypełniasz ją cyframi 0 lub 1 w określonym wzorze. Tak jak napisał kolega wyżej. Nie musisz tu używać żadnych potęg.

@sig jako, że maksymalny element tego ciągu to 65535 to lepiej jest zrobić statyczną tablicę niż za każdym razem liczyć od początku.

0

Kurcze Panowie mam już dzisiaj tak zlasowany mózg, że nie wiem jak się do tego zabrać... Słuszne uwagi.
Pomóżcie jeśli macie chwilę.

0

W pętli odejmujesz od N kolejne liczby naturalne tak długo jak liczba, którą masz teraz odjąć jest większa od pozostałej. Jeśli teraz twoje N jest równe 1 to zwracasz 1, w przeciwnym wypadku 0. Przełożone na C:

for (int i = 0; n > i; i++, n -= i);
printf("%d\n", n == 1);
0

W dalszym ciągu nie uzyskuje efektu.

1

Rozważmy sam ciąg.
110100100, albo inaczej:

1
10
100
1000
10000

Czyli. Pierwszy element to 1znak, drugi - 2 znaki, 3 - 3 znaki element numer n - n znaków. Korzystająz ze wzoru na sumę ciągu arytmetycznego:

S(n) = ((2a1 + (n-1)*r) / 2)n; - czyli w tym wypadku:

S(n) = ((2 + (n-1) * 1) / 2)n = ((n + 1) / 2)n = (n2 + n) / 2;

Możemy obliczyć na której pozycji kończy się liczba zawierająca (n-1) zer (i jedynkę).

a więc mamy -
S(n) + 1- pozycja jedynki z (n+1)'tej potęgi dziesiątki. (+1 - ze względu na syngature. wzór pokazuje nam gdzie kończy się dana potęga).

Pozycję znamy, nie wiemy która to potęga. A więc proste podstawienie:
S(n) + 1 = x
((n2 + n) / 2) + 1 = x (x - pozycja na wejściu).

Przekształcić ten wzór to chyba dasz radę? ;)
Wnioskując po komentarzach - nie potrafisz. Więc:

Wyznaczam n z powyższego:
n2 + n + 2 = 2x,
n2 + n - 2x + 2 = 0

d - delta.
d = 12 - 4 * 1 * (-2x + 2),
d = 1 -8x - 8,
d = 8x - 7.

interesuje nas tylko dodatni wynik:
n = (-1 + sqrt(d)) / 2.
n = (sqrt( 8x - 7 ) - 1) / 2.

Jeśli n wyjdzie całkowite, to na danym miejscu jest jedynka, jeśli nie - mamy zero :)

if( float( int( n ) ) == n )        // albo trudniej, ale szybciej:
cout << float( int( n ) ) == n;

Jeśli nie rozumiesz dlaczego tak jest to możesz zrobić tak jak @_13th_Dragon poniżej:
Jeżeli równanie jest spełnione - mamy jedynkę:

if( (n*(n+1) / 2) == x )            // albo trudniej, ale szybciej:
cout << (n*(n+1) / 2) == x ;

Do tego możesz łatwo rysować ciąg dalej. Wystarczy na podstawie ułamka określić, które to zero ( część po przecinku / n), dorysować pozostałe zera i dalej rysować 1 i n+1 zer, 2 i n+1 zer. Coś mogłem pochrzanić, bo nie rozpisywałem tego na kartce, ale ogólna zasada jest taka :)

No i pochrzaniłem. Nie wziąłem pod uwagę, że S(n) pokazuje na koniec danego elementu. @_13th_Dragon zrobił niżej poprawnie. Gdybyś kierował się tą zasadą mógłbyś mi nawet wytknąć błąd.
1

Wyjaśniać nie będę bo i tak tego nie chcesz, dla innych zaś może to (samodzielne dochodzenie jak to działa) być ciekawą rozrywką.

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

int main()
  {
   unsigned N;
   cin>>N;
   while(N--)
     {
      unsigned x;
      cin>>x;
      unsigned y=(unsigned)((sqrt(8*x-7)-1)/2);
      cout<<((y*(y+1)>>1)+1==x)<<' ';
     }
   return 0;
  }
0

Genialnie!
Dziękuję bardzo. Ja to robiłem w for'ach a Ty ująłeś tą w zaledwie kilku linijkach i za pomocą while...
Właśnie to jest ta magia wzorów, nie wpadłbym na to za cholerę.
Muszę przeanalizować Wasze odpowiedzi i zagłębić się w ich istotę.
Jeszcze wynik muszę wyświetlić na samym końcu po wprowadzeniu wszystkich liczb, a nie na bieżąco po wprowadzonej każdej z osobna.
Mogę na Was liczyć!

0
razielnr1 napisał(a):

Jeszcze wynik muszę wyświetlić na samym końcu po wprowadzeniu wszystkich liczb

  • kto ci powiedział taką bzdurę?
razielnr1 napisał(a):

Ja to robiłem w for'ach a Ty ująłeś tą w zaledwie kilku linijkach i za pomocą while

  • zamień while(N--) na for(unsigned n=0;n<N;++n) i nadal będzie działać, jak widzę nie załapałeś ani problemu ani rozwiązania.
    Gdyby choć trochę się znałeś na matematyce to zauważyłbyś że to dokładnie to samo co napisano wyżej przez @Ola Nordmann
    Gdyby trochę lepiej znałeś się na matematyce to dałbyś rady zoptymalizować to do:
#include <cmath>
#include <iostream>
using namespace std;
 
int main()
  {
   unsigned N;
   cin>>N;
   while(N--)
     {
      unsigned x;
      cin>>x;
      unsigned y=(unsigned)sqrt(8*x-7);
      cout<<(y*y==8*x-7)<<' ';
     }
   return 0;
  }
0

Niestety po wrzuceniu kodu do systemu komunikat jest następujący "Zła odpowiedź" ...

0

Popatrz na ograniczenia, możliwe że potrzebujesz unsigned long long a może potrzebujesz własną arytmetykę.
Z zadania: Kolejne N linii zawierają liczby naturalne i < 2^31 – numer pozycji w ciągu.
Czyli unsigned powinno wystarczyć jeżeli system 32 bitowy (tylko jeżeli 16 bitowy to potrzebny unsigned long).

0

Wklej tu zepsuty kod @_13th_Dragon swój kod, którego nie przepisałeś :>

0
 
#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;
 
int main(int argc, char *argv[])
{
    int n;
    cin >> n;
    for(int z=0; z<n; z++)
    {
              int i;
              cin >> i;
              int x = (int)sqrt(8*i-7);
              cout << (x == sqrt(8*i-7)) << " ";
    }
    return 0;
}
0

sqrt( 8x -7 ) to pierwiastek z delty w równaniu.
n jest równe: (-b + sqrt(d)) / 2.
równanie: (n2 + n) / 2 = x.

Masz sprawdzić czy równanie jest prawdziwe dla wynikowego n, albo sprawdzić, czy n jest całkowite. Przeczytaj jeszcze raz całą rozpiske.

0
  1. Zbędne dołączone #include <cstdlib>
  2. Zbędne parametry funkcji main()
  3. Niepotrzebna inkrementacja przyrostkowa, powinna być przedrostkowa
  4. Niepotrzebne podwójne obliczanie pierwiastka
  5. Bezsensowne użycie typów znakowych tam gdzie nie powinno być znaku
  6. Brakuje kropek po liczbach 8.
0

OMG!

1, 2 - biblioteka i parametry funkcji main są w standardowym tworzonym projekcie w Dev C++, więc to, że obie rzeczy są to nikomu nie szkodzi.
3 - postinkrementacja jak najbardziej pasuje do tej pętli... zmienienie na preinkrementację wymaga zmiany warunku w for.
4 - x == sqrt(8i-7)) <=> xx == 8*i-7 (napisane przez Ciebie).
5 - Biały znak owszem powinien być, więc nie bezsensowne.
6 - Jakich kropek...?

7 - zastanów się nim coś napiszesz.

EDIT: Fajnie, że pomagacie, ale przy tym też jesteście nieznośni :P

0

1, 2 - to nie znaczy, że masz je bezmyślnie zostawiać i zaszkodzą wydajności.
3 - Nie będziesz musiał. Panuje ogólne przekonanie, że preinkrementacja jest szybsza, ale w tej chwili normalny kompilator to zoptymalizuje poza przypadkiem przeładowania preinkrementacji obiektu, która będzie wolniejsza.
5 - Nie chodziło mu o typ znakowy char, tylko o typ oznaczony signed.
6 - Wyobraź sobie, że (float)(10/4) == 2, a (float)(10./4.) == 2.5.

7 - Zastanów się zanim coś napiszesz, bo czasem naprawdę lepiej dyskretnie milczeć, lub napisać: 'nie rozumiem' niż zrobić z siebie ignoranta :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1