作者Cidolfas ()
看板C_and_CPP
標題Re: [ACM ] Q412 WA (圓周率Pi估算)
時間Sat Aug 21 18:53:34 2010
※ 引述《cutecpu (可愛中央處理器)》之銘言：
: ※ 引述《jgnh (MUJI)》之銘言：
: : 題目 http://tinyurl.com/4q95so
: : 在N個正整數中任選兩數，則這兩數互質的機率約為 6/(π^2)
: : 題目是要求給你一堆測資，你要對每組測資輸出根據上式的π近似值到小數點後第6位，
: : 如果互質機率為0的話也要輸輸出 No estimate for this data set.
: : 以下是我的code，題目給的sample都正確但就是一直吃WA，
: : 麻煩大家囉～
不好意思，借用一段。
我也是題目給的sample都正確但就是一直吃WA，
請大家幫忙我找哪裡跟題目要求不合...謝謝。
中文翻譯：
http://luckycat.kshs.kh.edu.tw/homework/q412.htm
#include <iostream>
#include <iomanip>
#include <cmath>
#define LEN 52
using namespace std;
unsigned int gcd( unsigned int , unsigned int );
int main()
{
float PI;
unsigned int n; //設定要輸入幾組數，最多50
while( ( cin >> n ) && ( n != 0 ) )
{
unsigned int i;
unsigned int s[LEN] = {0} ;
for( i = 0 ; i < n ; i++)
cin >> s[i]; //將所輸入的數丟進 s[i] 中
unsigned int k = 0; //算所輸入的數中，互質的個數
for ( i = 0 ; i < n ; ++i )
for ( int j = i + 1 ; j < n ; ++j )
{
if ( gcd( s[ i ], s[ j ] ) == 1 ) //互質的話，k+1
k++;
}
PI = pow((double)( 3 * n *( n - 1 ))/ k , 1.0/2 ); //所估計的 pi 值
if ( k == 0 )
cout << "No estimate for this data set." << endl;
else
cout << setprecision(6) << setiosflags(ios::fixed) << PI << endl;
}
// system("pause");
return 0;
}
unsigned int gcd( unsigned int a , unsigned int b )//求最小公因數
{
unsigned int r = a % b;
while( r > 0 )
{
a = b ;
b = r ;
r = a % b ;
}
return b;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.85.191.24
※ 編輯: Cidolfas 來自: 219.85.191.24 (08/21 18:54)
→ pico2k:你的gcd演算法有問題... 08/21 19:51
→ x000032001:過了0.0 要用double 08/21 20:09
→ Cidolfas:感謝二位，另請教p兄，可以給個數值讓我試gcd嗎？thx 08/21 20:16
→ Cidolfas:因為我自己跑幾個都是對的 Orz 08/21 20:17
→ Cidolfas:x兄用的這網站好快，我喜歡～ 08/21 20:32
→ pico2k:我看錯了...*.* 08/21 20:52
推 andyisman:__gcd(a,b) 08/21 21:10
→ Cidolfas:嗯，請問樓上的是啥意思？ 08/21 21:25
→ suhorng:神秘內建的gcd函式 08/21 21:40
→ Cidolfas:唔，感謝各位！ 08/21 21:51
→ Powernow:公因數應該是求最大吧? 公倍數才是求最小不是? 08/22 12:51
→ Cidolfas:抱歉，是註記筆誤啦 08/22 15:51