例題 2-1 aabb 2-2 3n+1問題

例題 2-1 aabb 2-2 3n+1問題

例題2-1 aabb

輸出所有形如aabb的四位完全平方數（即前兩位數字相等，後兩位數字也相等）

#include 
#include 
#include  

int main(int argc, char *argv[])
{
  int i, j, n;
  double m;
  for(i = 1; i <= 9; i++)
     for(j = 0; j <= 9; j++)
     {
        n = i*1100 + j*11;
        //n = (i*10+i)*100 + j*10 + j;
        m = sqrt(n);
        if(floor(m+0.5) == m) printf("%d\n", n);
     }
  system("PAUSE");	
  return 0;
}

int main(int argc, char *argv[])
{
  int x, y;
  for(x = 33; x*x <= 9999; x++)
  {
     y = x*x;
     if(y/1000 == y/100%10 && y/10%10 == y%10)
        printf("%d\n", y);
  }
  system("PAUSE");	
  return 0;
}

總結：1 一組逆向的思維解決同一個問題

2 用變量n = a*1100 + b*11來儲存四位數

3 浮點運算會存在誤差。在進行浮點數誤差時，應考慮到浮點誤差 如 floor(m+0.5) == m

例題2-2 3n+1問題  
猜想：對於任意大於1的自然數n，若n為奇數，則將n變成3n+1，否則變成一半  
經過若干次這樣的變換，一定會使n變成1.例如3->10->5->16->8->4->2->1 輸入n，輸出變換的次數。n≤10^9.  樣例輸入：3  樣例輸出：7  

#include 
#include 

int main(int argc, char *argv[])
{
  unsigned  n, count = 0;
  scanf("%d", &n);
  while(n > 1)
  {
     if(n % 2 == 1)  { n = n + (n+1)/2; count += 2; continue;}
     else n >>= 1 ;
     count++;
  }
  printf("%d\n", count);
  
  system("PAUSE");	
  return 0;
}

總結：1 3n+1會溢出
2 一個臨時的解決方案是：因為n為奇數事3*n+1一定是偶數，下一步將其立刻除以2.如果將兩次操作一起做，可以在一定程度上緩解這個問題。有興趣的讀者可以試一 試。程序特點，要善於發現。
3 除以2 用右移操作

4 (3n+1)/2不如寫做 n + (n+1)/2,減少溢出的可能

例題2-3 階乘之和
輸入n，計算S=1!+2!+3!+……+n!的末6位（不含前導0），n≤10^6

#include 
#include 


int main()
{
    const int MOD = 1000000;
    int n;
    long long sum = 0, tem = 1;
    scanf("%d",&n);
    
    for (int i=1; i<=n; i++)
    {
        tem = tem*i%MOD ;
        sum = (sum+tem)%MOD;
    }
    printf("%d\n",sum);
    
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

總結：1 算術溢出，用每步除MOD的方式來解決
2 本題特性，當n>25時，結果就不變了，善於發現題目特點