记yahoo的一道笔试题

1920阅读　3评论2013-05-10　风箫夜吟
分类：C/C++

给定两个正整数a、b，求a/b的结果的小数点之后的第M个数字N(0-9)，出现在小数点之后的第几位。例如：a = 4， b = 7 ， a / b =  0.5714285714,我要求小数点之后的第二个7出现在什么位置，程序应该给我返回8。
ok？拿到这个题目，我们最开始想到的可不可以利用一般的除法获得结果，然后将结果装换成一个字符串进行字符的匹配，然后返回下标呢？
显然在这里是行不通的：
原因：
1、首先我们通常使用的double除法，位数的精度满足不了题目中的要求，题目中假如出现的是一个无限循环小数，我们无法记录它的所有小数点之后的数字。
2、即便我们记录下来了一定的位数，进行匹配的效率上也会存在很大的问题。
综上所述，我们应该选择另外一条路来解决这个问题，好吧，没有别的办法我们就用笔在纸上算一下这个算数除法的过程，在计算的过程中我们会发现：
1、所谓除法无非就是一个求商求余数的过程。
2、进一步来说所谓求商，实际上一个余数补零取整的操作。
3、求余数就是一个余数补零求模的操作。
看到以上三点我们就成功了一半，为什么说是一半呢：因为很多人看到这里，就开始写程序了，求模求商，然后将商放在一个数字里面进行匹配输出结果，最开始我也是这么去做的。但是，实际上这其中就包含了不能容忍的空间和时间上的损失。为什么这么说呢？
首先，我们知道其实小数分为两类：有限小数和无限小数，其实所谓的无限小数又分为循环小数和不循环小数。但是由分数构成的无限小数都是循环小数。为什么这么说呢？原因很简单就是我们从求小数的计算过程中可以看出，只要我们的余数出现了重复，商就进入了一个循环之中，所以我们没有必要将所有的商存储在一起，我们只需要存储一段未重复的商值，就可以通过M推导出商之中所有的数字出现的次序。
看到这里这个问题我们就解决了98%了，那余下的2%到底是什么？不要着急，当你写程序的时候就会发现这个问题了。现在我可以告诉大家：当我们的余数不重复的时候，商是有可能发生重复的，在一次循环中出现了商重复的情况我们需要记住重复重现的所有商的位置！
说了这么多还是上代码吧！

点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. using namespace std;
  5. int numPosAfterDecimalPoint(int firstNum, int secondNum, int code, int dest)
  6. {
  7.     if(firstNum < 0 || secondNum < 0 || code <= 0)
  8.         return -1;
  9.     set<int> remainder; //记录下余数
  10.     int temp;
  11.     int start; //循环起始时的余数
  12.     int counter = 0;
  13.     vector<int> quotient;
  14.     vector<int> cycleQuotient;
  15.     vector pos(secondNum, 0);
  16.     temp = firstNum % secondNum; //当被除数大于除数的时候先要进行一次取模的运算，如果为零则直接返回0
  17.     if(temp == 0)
  18.     {
  19.         return 0;
  20.     }
  21.     remainder.insert(temp);//将余数压入set集合
  22.     while(true)
  23.     {
  24.         quotient.push_back(temp * 10 / secondNum); //将商放入一个数组
  25.         temp = temp * 10 % secondNum;
  26.         if(remainder.count(temp)) //判断余数是否发生了重复，假如发生了重复将重复部分的商压入cycleQuotient
  27.         {
  28.             start = temp;
  29.             do{
  30.                 cycleQuotient.push_back(temp * 10 / secondNum);
  31.                 temp = temp * 10 % secondNum;
  32.             }while(temp != start);
  33.             //cout << "cycleQuotient: " << cycleQuotient.size() << endl;
  34.             break;
  35.         }
  36.         remainder.insert(temp);
  37.     }
  38.     //cout << "quotient.size(): " << quotient.size() << endl;
  39.     vector<int>::size_type it = 0;
  40.     while(it != quotient.size()) //在一次循环中查找目标元素
  41.     {
  42.         if(quotient[it] == dest)
  43.         {
  44.             counter++;
  45.             if(counter == code)
  46.                 return ++it;
  47.         }
  48.         it++;
  49.     }
  50.     if(counter == 0)
  51.         return 0;
  52.     else if(counter < code) //判断要求的位置是否超出了一次循环，假如超出计算循环商中目标数字的位置
  53.     {
  54.         int i = 0;
  55.         vector<int>::size_type it = 0;
  56.         while(it != cycleQuotient.size())
  57.         {
  58.             if(cycleQuotient[it] == dest)
  59.             {
  60.                 pos[++i] = it + 1;
  61.             }
  62.             it++;
  63.         }
  64.         if(pos[1] == 0)
  65.             return 0;
  66.         if((code - counter) >= i && (code - counter)% i == 0)
  67.         {
  68.             return quotient.size() + ((code -counter) / i - 1) * cycleQuotient.size() + pos[i];
  69.         }
  70.         else if((code - counter) < i)
  71.             return quotient.size() + pos[(code - counter) % i];
  72.         else
  73.         {
  74.             return quotient.size() + ((code - counter) / i - 1) * cycleQuotient.size() + pos[(code - counter) % i];
  75.         }
  76.     }
  77. }
  78. int main() {
  79.     int firstNum; //被除数
  80.     int secondNum; //除数
  81.     int code; //表示第次出现的目标数字
  82.     int dest; //目标数字
  83.     cout << "firstNum: " << endl;
  84.     cin >> firstNum;
  85.     cout << "secondNum: " << endl;
  86.     cin >> secondNum;
  87.     cout << "code: " << endl;
  88.     cin >> code;
  89.     cout << "dest: " << endl;
  90.     cin >> dest;
  91.     cout << "result: " << numPosAfterDecimalPoint(firstNum, secondNum, code, dest) << endl;
  92.     return 0;
  93. }
ok 现在代码写完了，你看懂了么？
上一篇：写一个寻找最大重复字串的算法
下一篇：new 和 malloc的区别

文章评论