[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Производ  XML
Forum Index » Задачи од национални натпревари
Author Message
VasilK



Joined: 30/05/2010 12:29:35
Messages: 17
Offline

Може ли некој да ми каже зашто кога внесувам 0.99 и 0.53 во програмава наместо 0.99 чита 0.99000001 и наместо 0.53 чита 0.529999971??
ај за 0.99 не е проблем али после коа го множам 0.53 со 100 и го претварам во int ми го заокружува на 52
Фала однапред

#include <iostream>
using namespace std;
int main()
{
float old_price, new_price;
cin >> old_price >> new_price;
old_price*=100;
new_price*=100;
int price1=(int)old_price, price2=(int)new_price, nzd, nzs;
while(1==1)
{
if(price1==0)
{
nzd=price2;
break;
}
else if(price2==0)
{
nzd=price1;
break;
}
else
{
price1=price1%price2;
int temp;
temp=price1;
price1=price2;
price2=temp;
}
}
nzs=(int)old_price*(int)new_price/nzd;
int M, N;
M=nzs/(int)old_price;
N=nzs/(int)new_price-M;
cout << "KUPI " << M << " DOBIJ " << N << " GRATIS" << endl;
}
Bojan Kostadinov



Joined: 08/10/2009 13:56:21
Messages: 89
Offline

Така е бидејќи float и double имаат ограничена прецизност (можеш повеќе да прочиташ тука - http://en.wikipedia.org/wiki/Floating_point#IEEE_754:_floating_point_in_modern_computers). На пример, ти во програмата користиш податочен тип float кој користи 32 бита за чување на вредноста (од кои 23 ја даваат прецизноста, 1 е за знак, другите се за експонент), и со кој прецизно можат да се претстават околу 7 децимални цифри. Нормално, со double може да се добие поголема прецизност (double користи 64 бита за чување на вредноста), но и тој има ограничена прецизност... Мој предлог ти е да го заборавиш float и секогаш кога имаш потреба од реални броеви да си користиш double (или long double - тоа би требало да има уште поголема прецизност).

Она што треба да се знае е дека:
      - float, double, ..., не ја чуваат вистинската вредност, туку имаат одредена прецизност.
      - Секој 32-битен цел број може да се претстави со double (64-бита) без загуба на прецизноста.
      - Кога веќе еднаш ќе почнат да се вршат пресметки со double, голема е веројатноста дека ќе се воведат грешки (загуба на прецизноста).

Повеќе можеш да прочиташ тука - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=integersReals.

Јас обично ги користам функциите round(num) и floor(num+EPS), или (int)(num+EPS), кога сакам да претворам некој реален број во цел. EPS e некоја мала вредност која ќе ни помогне да ги избегнеме овие т.н. rounding errors.
VasilK



Joined: 30/05/2010 12:29:35
Messages: 17
Offline

Фала, тоа го реши почетниот прболем али сеа ми паѓа на тест примери каде што нзс е поголемо од 2^32-1
пробав nzs да го декларирам како long long наместо int али пак не иде...

#include <iostream>
using namespace std;
int main()
{
float old_price, new_price;
cin >> old_price >> new_price;
old_price*=100;
new_price*=100;
int price1=(int)old_price, price2=(int)new_price, nzd;
while(1==1)
{
if(price1==0)
{
nzd=price2;
break;
}
else if(price2==0)
{
nzd=price1;
break;
}
else
{
price1=price1%price2;
int temp;
temp=price1;
price1=price2;
price2=temp;
}
}
long long nzs;
nzs=(int)old_price*(int)new_price/nzd;
int M, N;
M=nzs/(int)old_price;
N=nzs/(int)new_price-M;
cout << nzs << endl;
cout << "KUPI " << M << " DOBIJ " << N << " GRATIS" << endl; system("pause");
}
Bojan Kostadinov



Joined: 08/10/2009 13:56:21
Messages: 89
Offline

Направи го следното:
  1. Замени го float со double.
  2. Наместо директно кастирање од double во int после операции со реални броеви, користи EPS (види претходен коментар) или round
            int price1=(int)round(old_price), M=nzs/round(old_price), ....
  3. Иако ја имаш дефинирано променливата nzs да е од тип long long, сепак сите променливи од десната страна на = (операторот за доделување) се int, па и операциите од таа страна ќе се извршат како операции со int (потоа се врши претворање во long long). Дополнително, можеш НЗС(A,B)=A*B/НЗД(A,B), да го замениш со НЗС(A,B)=A*(B/НЗД(A,B)), бидејќи НЗД(A, B) го дели B. Или пак, можеш A*B/НЗД(A,B) да го пресметаш преку операции со реални броеви, а потоа само да го претвориш резултатот во цел број (доколку си сигурен дека прецизноста на double е доволна).





(Off-topic) Задачата може да се реши и без користење на long long и наоѓање на НЗС.

This message was edited 1 time. Last update was at 28/12/2010 18:57:37

VasilK



Joined: 30/05/2010 12:29:35
Messages: 17
Offline

Фала, ова го реши проблемот и ми се разјаснија некои ствари
иначе по грешка сум пратил некој постар код, затоа тие сеуште ми беа float..
Goran1



Joined: 22/09/2010 23:02:31
Messages: 18
Offline

program proizvodd;
var p,n,vkupno:real;
i:integer;
begin
readln(p);
readln(n);
i:=0;
vkupno:=0;
repeat
vkupno:=vkupno+p;
i:=i+1;
until vkupno/n=trunc(vkupno/n);
write('KUPI ',i,' DOBIJ ',vkupno/n-i:0:0,' GRATIS');
readln;
end.

Moze li nekoj sto raboti vo Pascal da mi kaze sto da promenam da ne go nadminuva vremenskiot limit, bidejki mi raboti samo na 4 slucai, a na drugite go nadminuva limitot.
MOI



Joined: 07/07/2010 16:31:48
Messages: 447
Offline

Goran1 wrote:Moze li nekoj sto raboti vo Pascal da mi kaze sto da promenam da ne go nadminuva vremenskiot limit, bidejki mi raboti samo na 4 slucai, a na drugite go nadminuva limitot.

1. Пред да испратиш код на форумот - селектирај го и кликни на копчето "Code". Така е поубаво и почитливо
2. Поставуваш прашање во некоја тема (на пример, "Производ") а не си прочитал што е напишано во неа (прочитај го второто мислење). Зошто некој би се мачел да ти го чита и тестира кодот, кога ти не си одвоил 5 минути за да прочиташ што е напишано во темава?!
3. Не поставувај исто прашање во две различни теми. (Ја избришав темата што си ја отворил во делот "Паскал")

Сега, што се однесува до програмата, бидејќи реалните броеви не се чуваат егзактно, прво треба да го промениш начинот на кој споредуваш два реални броеви за еднаквост (наместо A=B, треба да ставиш abs(A-B) < *некоја мала вредност*):

Сега, кога ќе ја тестираш програмата дадена погоре, ќе сватиш дека не ти е добар алгоритамот што го користиш (веќе не дава "Надминат временски лимит" туку "Погрешен одговор"). Наместо дали diff=0, треба да проверуваш дали diff е цел број. Еве ја поправената програма:

Најдобро решение е воопшто да не вршиш операции врз реални броеви - од кога ќе ги прочиташ броевите, помножи ги со 100 и кастирај/претвори ги во longint. Потоа, врши (егзактни) операции врз цели броеви.
Goran1



Joined: 22/09/2010 23:02:31
Messages: 18
Offline

Благодарам за сугестиите. 1 не го применував бидејќи сум нов на форумов и го немав забележано копчето Code, за 2 не ги разгледав коментарите до крај, туку само меѓу редови, бидејќи пристапот на решавање беше различен од мојот (со НЗС и НЗД) и првичното прашање не сметав дека е поврзано со мојот проблем (што е моја грешка) и се извинувам. Темата ја поставив првин во Pascal, но бидејќи потоа видов дека веќе има тема за истата задача решив да постирам и овде. Благодарам и за сугестиите во врска со задачата, ова со споредувањето на реални броеви веројатно ми правело проблеми и во други задачи со runtime error, баш ќе пробам да ги пререшам. Ми се разјаснија нештата откако ги прочитав внимателно коментарите и PDF документот со чести грешки на натпревари. Добар документ
Sanjas



Joined: 09/12/2012 12:27:06
Messages: 1
Offline



na nekoi test slucai vika netocno...

This message was edited 1 time. Last update was at 19/02/2014 21:49:11

[Yahoo!]
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

1. Користи [code] тагови, не фонт 16ка за код.

2. Провери ги тест примерите локално во дебагер и види зошто е неточно.
darijan2002



Joined: 20/10/2012 17:50:43
Messages: 5
Offline

Bojan Kostadinov wrote:Направи го следното:
  1. Замени го float со double.
  2. Наместо директно кастирање од double во int после операции со реални броеви, користи EPS (види претходен коментар) или round
            int price1=(int)round(old_price), M=nzs/round(old_price), ....
  3. Иако ја имаш дефинирано променливата nzs да е од тип long long, сепак сите променливи од десната страна на = (операторот за доделување) се int, па и операциите од таа страна ќе се извршат како операции со int (потоа се врши претворање во long long). Дополнително, можеш НЗС(A,B)=A*B/НЗД(A,B), да го замениш со НЗС(A,B)=A*(B/НЗД(A,B)), бидејќи НЗД(A, B) го дели B. Или пак, можеш A*B/НЗД(A,B) да го пресметаш преку операции со реални броеви, а потоа само да го претвориш резултатот во цел број (доколку си сигурен дека прецизноста на double е доволна).





(Off-topic) Задачата може да се реши и без користење на long long и наоѓање на НЗС.



ова е точното решение на задачата
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team