[C/C++] ACM - 10539 - Almost Primes Numbers

這題的 long long 真是超級機車的, 遇到了一些奇怪的 coding 問題, submit 了大概快三十次才 AC 吧 = =

 

[問題一]

 

quicksort 裡的 compare function, 如果型態不是 long long,

 

以下兩種寫法都行, 只需對應參數的型態.

 

但如果是 long long 就只能用寫法二了, 真不知道為什麼? @@

 

寫法一 :

 int compare( const void *a, const void *b)
{  return (long long *)a - (long long*)b) ; }

 

寫法二 :

int compare(const void *a,const void *b)
{
   long long *c, *d;
   c=(long long *)a;
   d=(long long *)b;
  
   if(*c>*d)
      return 1;
   else if(*c==*d)
      return 0;
   else
      return -1;
} 

 

[問題二]

 

寫法一跟寫法二的意思是一樣的, 可是寫法一和寫法二 nonprime[] 裡存放的東西卻不一樣.

 

寫法一才是正確的, 寫法二卻不是?

 

寫法一:

long long temp;

long long nonprime[80080];

for (i = 0, k = 0; k < 80070; i++)
  {
  temp = prime[i];
  while ((temp *= prime[i]) <= 1e12)
    { nonprime[k++] = temp; }
  }

 

寫法二:

long long nonprime[80080];

for (i = 0, k = 0; k < 80070; i++)
  {
  nonprime[k] = prime[i]*prime[i];  // prime[i] * prime[i]  都會小於等於 1e12,  所以寫法一的迴圈也會跑  while (nonprimep[k] * prime[i] <= 1e12)
    {

    nonprime[k+1] = nonprime[k] * prime[k];

    k++; 

    }
   }

 

[心得]

 

突然發現 cout 可以正確的印出 long long 的值,

 

以後遇到 long long 的題目還是用 C++ 寫好了.

[C/C++] 函式 pow( ) 的用法

這是 math.h 裡的註解

Excess precision when using a 64-bit mantissa for FPU math ops can
cause unexpected results with some of the MSVCRT math functions.  For 
example, unless the function return value is stored (truncating to
53-bit mantissa), calls to pow with both x and y as integral values
sometimes produce a non-integral result.                                                                               
One workaround is to reset the FPU env to 53-bit mantissa
by a call to fesetenv (FE_PC53_ENV).  Amother is to force storage
of the return value of individual math functions using wrappers.
NB, using these wrappers will disable builtin math functions and
hence disable the folding of function results at compile time when
arguments are constant.

最好不要拿 pow( ) 直接做 Boolen 運算

=================================================

int n = 3;

double temp;

i f ( pow(10, n) == 1000.0 )  <-- which seems alright, but BAD!!

  DO SOMTHING....

temp = pow(10, n);

i f ( temp == 1000.0 )  <-- need another storage, but BETTER!!

  DO SOMTHING....

=================================================

[C/C++] ACM - 628 - Passwords

1st is a Russian who solved 1978 problems,

3rd is a Japanese who solved 1790 problems,

21nd is  a Taiwanese who solved 1278 problems,

1389th is me who solved 170 problems,

They are far far far  away from me.......

這題並不會很難, 但是用到 pow() 函式的時候卻發現了有趣的問題.

情況一:

pow(10, 2) == 100    <= TRUE

pow(10, 3) == 1000  <= TRUE

pow(10, 4) == 10000 <= TRUE

情況二:

n = 2;

pow(10, n) == 100     <= TRUE

n = 3;

pow(10, n) == 1000   <= FALSE

n = 4;

pow(10, n) == 10000 <= TRUE

不知道為什麼會這樣哩  : P

去問問數值分析老師好了, 哈哈.