Nie jesteś zalogowany.
Jeśli nie posiadasz konta, zarejestruj je już teraz! Pozwoli Ci ono w pełni korzystać z naszego serwisu. Spamerom dziękujemy!

Ogłoszenie

Prosimy o pomoc dla małej Julki — przekaż 1% podatku na Fundacji Dzieciom zdazyć z Pomocą.
Więcej informacji na dug.net.pl/pomagamy/.

#1  2007-05-17 14:41:13

  pablo - Członek DUG

pablo
Członek DUG
Skąd: Białystok
Zarejestrowany: 2006-04-12
Serwis

[c++/python/inne] Suma

Kod:

Twoim zadaniem jest napisać program, który wyliczy sumę wszystkich liczb całkowitych leżących pomiędzy 1 a N (włącznie).
Wejście

Pierwsza linia zawiera dokładnie jedną liczbę naturalną n, 1<=n<=200000, będącą liczbą zestawów danych. W n kolejnych liniach występują poszczególne zestawy danych. Każdy zestaw składa się z jednej liczby całkowitej N.
Wyjście

Program powinien wypisać na standardowe wyjście n linii. I-ta linia powinna zawierać sumę wszystkich liczb całkowitych leżących pomiędzy 1 a N. Gwarantujemy, że wartość bezwzględna sumy nie przekroczy 2^31.
Przykład

Input:
4
3
2
5
7

Output:
6
3
15
28

Oto treść zadania na SPOJ.pl które mam rozwiązać. Wiem, że jest ono wmiarę proste, ale dopiero zaczynam zabawę:)
No i mam z nim pewien problem, w C++ napisałem dwa programy

Kod:

#include <iostream>
#include <cmath>
 
using namespace std;
int n,j;
long a;
int main ()
{
cin>>n;
    for (j=1;j<=n;j++)
        {
            cin>>a;
            a=((1+a)*a/2);
            cout<<a<<endl;
         }
 return 0;
}

i

Kod:

#include <iostream>
#include <cmath>

using namespace std;

int a,t[10],i,n,j;
int main ()
{
for (i=1;i<=10;i++)
{
t[i]=t[i-1]+i;
}
cin>>n;
for (j=1;j<=n;j++)
{
cin>>a;
cout<<t[a]<<endl;
}
return 0;
} 

I z tym pierwszym jest błędna odpowiedź (float przy większych liczbach zwraca u mnie do kilku cyfr i potem +e jakieś dwie cyfry, jak dam int to też jest źle bo w niektórych przypadkach wynik wychodzi ujemny), w drugim przypadku program działa u mnie na komputerze, ale tam wyskakuje błąd wykonania (SIGSEGV) - naruszenie ochory pamięci.

Próbowałem zrobić w pythonie (nic nie umiem) i się udało (w sumie banał) jednak na spoju przekroczony jest czas wykonania (jak wstawiłem w programie baardzo duże(maksymalna ilość prób i liczba przewyszająca 2^31) dane to user time był na poziomie 1,25 sekundy)

Kod:

#!/usr/bin/env python
j=input()
for i in range(j):
    k=input()
    k=((1+k)*k/2)
    print k

Pusto :)

Offline

 

#2  2007-05-17 15:24:00

  chyl-o - Członek DUG

chyl-o
Członek DUG
Skąd: Lublin
Zarejestrowany: 2006-04-04
Serwis

Re: [c++/python/inne] Suma

To np:  2e-7 costam oznacza 2*10^-7. Co do drugiej sprawy, to zakres jak przekroczysz to faktucznie liczenie zaczyna się od poczaŧku. Jeśli masz typ unsigned to od zera, jak nie to od jakiejś wartości ujemnej, to zależy od tego jaki typ rozpatrujemy.

Typ long int  jest większy od int, więc jak nie działa poprawnie na typie long to nie liczyłbym że zadziała na int.

jeśli masz obliczyć sumę liczb całkowitych to po co wchodzisz w typy zmiennoprzecinkowe ?

Jeszcze jedna uwaga, żeby sobie zobaczyć jak dużo liczb dany typ może pomieścić u Ciebie wykonaj coś takiego:

Kod:

cout << "dlugosc int: " << sizeof( int ) << endl;

// edit:
Lorenzo, z tego co widzę w kodzie pierwszego programu, to jest tam zmienna która domyślam się że ma przechowywać sumę i jest typu long int( c++ przy specyfikatorach short, long dopuszcza pominięcie int'a, ale to wpływa ujemnie na czytelność kodu ), ale za chorobę nie mogę się domyśleć dlaczego jest suma liczona w taki dziwny sposób...

A drugiego przykładu to w ogóle nie rozumiem.  Jeśli na początku nie wiadomo ile będziesz miał danych wejściowych, a chcesz je przechować to możesz skorzystać ze stosu, albo prościej vectora w c++. Do zwykłej sumy według mnie nie trzeba takich cudaków tworzyć.


Registered Linux User: #417111
http://chyl.org/pub/images/dug_button.png

Offline

 

#3  2007-05-17 15:27:53

  Lorenzo - Moderator

Lorenzo
Moderator
Zarejestrowany: 2005-12-23

Re: [c++/python/inne] Suma

chliw-o:wiem, doczytałem. Pisanie postów, po alkoholu nie jest zbyt mądre ;-)

//edit: Jeśli dobrze zrozumiałem treść ;-) to przykładowy kod w C wygląda tak:

Kod:

#include <stdio.h>

int main()
    {
                long lintSum=0;
                int intCounter;
                int intNumber;
                
                system("clear");
                printf("Podaj liczbęn");
                scanf("%d",&intNumber);

                for(intCounter=1;intCounter<intNumber+1;intCounter++)
                        {
                                lintSum+=intCounter;
                                printf("%ldn",lintSum);
                         }              //end of for loop
                         
                printf("Suma kolejnych %d wynosi %ldn",intNumber,lintSum);
                
                return 0;
                
     }          //end of main

Offline

 

#4  2007-05-17 15:58:42

  pablo - Członek DUG

pablo
Członek DUG
Skąd: Białystok
Zarejestrowany: 2006-04-12
Serwis

Re: [c++/python/inne] Suma

Kod:

cout << "dlugosc int: " << sizeof( int ) << endl;

To zawsze daje mi 4. niezależnie czy int czy float. Co do zmiennoprzecinkowych to akurat w tej "wersji" programu tak mam, jak wcześniej pisałem na integer jest prawie dobrze... z wyjątkiem tego, że ten przy niektórych wynikach są liczby ujemne...


Pusto :)

Offline

 

#5  2007-05-17 16:00:47

  chyl-o - Członek DUG

chyl-o
Członek DUG
Skąd: Lublin
Zarejestrowany: 2006-04-04
Serwis

Re: [c++/python/inne] Suma

No a w c++ ja bym to rozwiązał podobnie:

Kod:

// Sumowanie liczb
#include <iostream>

using namespace std;

int main()
{
unsigned long int suma = 0;
int maxNum;
cout << "Podaj ile liczb mam zsumowac: ";
cin >> maxNum;
for( int i = 1; i <= maxNum; i++ )
suma += i;
cout << "Suma " << maxNum << " liczb calkowitych wynosi " << suma << endl;
}//:~

Tylko teraz znowu myślę, że trochę nie tak rozwiązaliśmy, bo tam trzeba było zająć się sumą liczb całkowitych, więc przydałaby się pewnie kontrola, czy podana liczba jest dodatnia czy ujemna i odpowiednio sterować licznikiem pętli...

// edit:
Pablo a spróbuj sobie sprawdzić ilość zajmowanej pamięci przez typy:

Kod:

unsigned int
unsigned long int
double
long double

// edit2:
W takim wypadku jak powyżej to można sobie jeszcze jeden bit zajumać ze znaku i rozpatrywać  tylko liczby dodatnie, co podwaja maksymalny zakres.


Registered Linux User: #417111
http://chyl.org/pub/images/dug_button.png

Offline

 

#6  2007-05-17 16:49:40

  pablo - Członek DUG

pablo
Członek DUG
Skąd: Białystok
Zarejestrowany: 2006-04-12
Serwis

Re: [c++/python/inne] Suma

Powiem tak, postęp teraz program działa prawidłowo tyle że wyskakuje

Kod:

przekroczono limit czasu 

Tak samo jak w pythonie i w bashu:)


Pusto :)

Offline

 

#7  2007-05-18 04:43:36

  KARQL - Członek DUG

KARQL
Członek DUG
Zarejestrowany: 2006-03-06

Re: [c++/python/inne] Suma

Siema. Nie chce mi sie teraz czytac calego topicu bo juz pozno, a do tego mam troche lini kodu za soba:D

Lubie takie zadania, wiec jak sie obudze to edytuje tego posta i napisze Ci jak to mozesz rozwalic:D

Pozdro.


http://img254.imageshack.us/img254/1225/gentoobar1rs9.png

Offline

 

#8  2007-05-18 07:43:23

  pablo - Członek DUG

pablo
Członek DUG
Skąd: Białystok
Zarejestrowany: 2006-04-12
Serwis

Re: [c++/python/inne] Suma

Kod:

 W tablicy n liczb całkowitych dodatnich znajdź wartość najbliższą, co do modułu, warości średniej.
Input

Najpierw t - liczba testów. W kolejnych liniach, dla każdego testu, liczba n i n liczb.
Output

Dla każdego testu, w kolejnych liniach, jedna liczba - pierwszy element tablicy, którego wartość jest najbliższa wartości średniej.
Example

Input:
2 
4 1 2 3 4 
4 4 3 2 1

Output:
2
3

Kod:

#include <iostream>
#include <cmath>
 
using namespace std;
int n,l,a,i,t[10000];
float s,d,t1[10000],g,h;
int main()
{
cin>>n;
for (l=1;l<=n;l++)
    {
        cin>>a;
        for (i=1;i<=a;i++)
            {
                cin>>t[i];
                s=s+t[i];
            }
        h=10000;
        s=s/a;
        for (i=1;i<=a;i++)
            {
                if (t[i]>s)
                    t1[i]=t[i]-s;
                        else
                    t1[i]=s-t[i];
                if (t1[i]<h)
                    {
                        g=t[i];
                        h=t1[i];
                    }
            }
    cout<<g<<endl;
    }
return 0;
}

Oto zadanie i moje rozwiązanie. Nie wiem czemu wyskakuje błędna odpowiedz:( Sprawdzałem różne możliwości i zawsze dobre wyniki wychodzą:P


Pusto :)

Offline

 

#9  2007-05-18 11:15:56

  KARQL - Członek DUG

KARQL
Członek DUG
Zarejestrowany: 2006-03-06

Re: [c++/python/inne] Suma

W pierwszym zadaniu nie podales limitow czasu i pamieci. To bardzo duzo mowi, jaki tok masz obrac.

Nie podales tego, wiec zrobilem pod to zebys sie wyrabial z czasem.

Kod:

#include <cstdio>

int main()
{
        int sumy[65536];
        int n, i;

        for ( i = 0; i < 65536; i++ )
        {
                sumy[i] = i + sumy[i - 1];
        }

        scanf("%i", &n);

        while ( n-- > 0 )
        {
                scanf("%i", &i);
                printf("%in", sumy[i]);
        }

        return 0;
}

Na pewno jak pogram jest testowany to dostaje zestawy dla duzej liczby sum, wiec jesli bys liczyl za kazdym razem to to troche trwa. Np bedzie zesta 10000 i 65535 tysiac razy. To na pewno Ci nie zdarzy. Dla tego tablicujesz sobie wyniki. Przy pisaniu tego sprawdzilem, ze dla wiekszych jak 65535 jest wieksze niz 2*31, stablicowalem te wyniki i pozniej tylko je wyswietlam.

Pamieci powinno starczyc bo to jest 65536 * (bajty) / 1024(wynik w KB) = 256, limity sa przewaznie wieksze.

Dalej z takich komentarzy.
Nie uzywaj strumieni w cpp sa duzo wolniejsze. Do zadan tego typu uzywa sie tylko printf i scanf.

Kod:

cout << "dlugosc int: " << sizeof( int ) << endl;

To zawsze daje mi 4. niezależnie czy int czy float. Co do zmiennoprzecinkowych to akurat w tej "wersji" programu tak mam, jak wcześniej pisałem na integer jest prawie dobrze... z wyjątkiem tego, że ten przy niektórych wynikach są liczby ujemne...

Bo ma Ci dawac 4 bo to jest liczba bajtow jakie zajmuje w pamieci dany typ.

Jesli chcesz sprawdzic jaka maksymalna liczbe mozesz dac to robisz tak.
Dla signed
od -2^(8 * sizeof(typ) - 1) do 2^(8 * sizeof(typ) - 1) - 1 (-1 na koncu bo jeszcze zero)

Dla unsigned
od 0 do 2^(8 * sizeof(typ)) -1 (-1 jw.)

Nastepne:
W tych zadaniach *nie* sprawdzacie poprawnosci danych! Wejscie jest zawsze dobre. W takich zadaniach liczy sie algorytm, nie robi sie zadnych sprawdzan, komunikatow czy innego syfu. Czytasz wejscie i wypuwasz wyjscie wszystko.

Na to zadanie co teraz dales nie chce mi sie patrzyc. Napisalem to teraz na szybkiego bo ide odpowietrzac hamulce w samochodzie. Pozatym to nie chodzi o to, zebysmy tobie rozwiazywali zadania bo to nie ma sensu.

Co do takich stron to polecam jeszcze http://opss.safo.biz

Pozdrawiam.


http://img254.imageshack.us/img254/1225/gentoobar1rs9.png

Offline

 

#10  2007-05-18 14:35:59

  pablo - Członek DUG

pablo
Członek DUG
Skąd: Białystok
Zarejestrowany: 2006-04-12
Serwis

Re: [c++/python/inne] Suma

Wrr. Twoje zadanie ma ten sam problem co moje:P
błąd wykonania (SIGSEGV)

Co tego pierwszego zadania
Limit czasu:    5s
Limit długości źródła:    50000B


Pusto :)

Offline

 

#11  2007-05-18 15:27:53

  KARQL - Członek DUG

KARQL
Członek DUG
Zarejestrowany: 2006-03-06

Re: [c++/python/inne] Suma

Daj link do tego zadania.


http://img254.imageshack.us/img254/1225/gentoobar1rs9.png

Offline

 

#12  2007-05-18 15:30:57

  pablo - Członek DUG

pablo
Członek DUG
Skąd: Białystok
Zarejestrowany: 2006-04-12
Serwis

Re: [c++/python/inne] Suma

To będzie to zadanie
http://opss.safo.biz/?menu=comp&sub=prob&comp=0&prob=1011
te same co no spoju


Pusto :)

Offline

 

#13  2007-05-18 16:04:01

  KARQL - Członek DUG

KARQL
Członek DUG
Zarejestrowany: 2006-03-06

Re: [c++/python/inne] Suma

Na safo zrobilem juz dawno temu, jak patrze teraz w source, to nawet nie pamietalem, ze robilem to takim sposobem:D

Tutaj trzeba uzyc wzoru.

Kod:

#include <stdio.h>

int main(void)
{
        int d,n,an;

        scanf("%i", &d);

        while (d-- > 0)
        {
                scanf("%i",&an);

                (an >= 1) ? (n = an) : (n = -an + 2);

                printf("%lin", (long int)((1 + an) / 2.0 * (float)n));
        }

        return 0;
}

Rozwiazanie w czystym C.

Ten wczesniejszy zwracal segmentation fault. Bo tresc jest troche nie jasna i sie zapomina o tym, ze moze byc od -liczba do 1:D Wiec jak sie odwolywal do ujemnych indeksow to musial wyskoczyc:D Jakby go troche poprawil to dzialal by tez ta metoda, ale z tym wzorem chyba lepsza jest.

Jak mozesz to daj linka na spoj.


http://img254.imageshack.us/img254/1225/gentoobar1rs9.png

Offline

 

#14  2007-05-18 19:15:53

  pablo - Członek DUG

pablo
Członek DUG
Skąd: Białystok
Zarejestrowany: 2006-04-12
Serwis

Re: [c++/python/inne] Suma

Niestety te zadanie nie jest dostępne dla ogułu.


Pusto :)

Offline

 

#15  2007-05-20 06:08:18

  T.N. - Użytkownik

T.N.
Użytkownik
Zarejestrowany: 2005-09-01

Re: [c++/python/inne] Suma


I z tym pierwszym jest błędna odpowiedź (float przy większych liczbach zwraca u mnie do kilku cyfr i potem +e jakieś dwie cyfry, jak dam int to też jest źle bo w niektórych przypadkach wynik wychodzi ujemny)

To daj long long int.

Offline

 

Stopka forum

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson
Nas ludzie lubią po prostu, a nie klikając w przyciski ;-)