两个数

设有两个自然数X、Y,2<=X<=Y<=99,S先生知道这两个数的和S,P先生知道这两个数的积 P ,他们二人进行了如下对话:

S:我确信你不知道这两个数是什么,但我也不知道。

P: 一听你说这句话,我就知道这两个数是什么了。

S: 我也是,现在我也知道了。

现在你能通过他们的会话推断出这两个数是什么吗?(当然,S和P先生都是非常聪明的)


   1 #include <cstdlib>
   2 #include <vector>
   3 #include <algorithm>
   4 #include <iostream>
   5 using namespace std;
   6 struct comb{
   7     int x;
   8     int y;
   9     int sum;
  10     int product;
  11     bool erased;
  12 };
  13 
  14 bool bysum(const comb &a, const comb &b) {
  15     return a.sum < b.sum;
  16 }
  17 
  18 bool byproduct(const comb &a, const comb &b) {
  19     return a.product < b.product;
  20 }
  21 bool byerased(const comb &a, const comb &b) {
  22     return a.erased < b.erased;
  23 }
  24 
  25 int main() {
  26     int i, j;
  27     const int max = 99;
  28     vector<comb> combines;
  29     
  30     //init all combinations
  31     comb c;
  32     c.erased = false;
  33     for (c.x = 2; c.x <= max; c.x++) {
  34         for(c.y = c.x; c.y <= max; c.y++) {
  35             c.sum = c.x+c.y;
  36             c.product = c.x*c.y;
  37             combines.push_back(c);
  38         }
  39     }
  40     
  41     //remove combinations not consist with first clause
  42     sort(combines.begin(), combines.end(), bysum); 
  43     for(i = 0; i < combines.size();) {
  44         for(j = i+1; j < combines.size() && combines[i].sum == combines[j].sum;j++)
  45             ;
  46         if(j == i+1) {
  47             combines[i].erased = true;
  48         } else {
  49             int m;
  50             for(m = i; m < j; m++) {
  51                 int k;
  52                 for(k = 0; k < combines.size(); k++)
  53                     if(k!=m && combines[m].product == combines[k].product)
  54                         break;
  55                 if(k == combines.size()) {
  56                     for(int a = i; a < j; a++)
  57                         combines[a].erased = true;
  58                     break;
  59                 }
  60             }
  61         }
  62         i = j;
  63     }
  64     
  65     //accually remove combinations
  66     sort(combines.begin(), combines.end(), byerased);
  67     for(i = 0; i < combines.size() && !combines[i].erased;i++);
  68     combines.erase(combines.begin()+i, combines.end());
  69 
  70     //remove combinations not consist with second clause
  71     sort(combines.begin(), combines.end(), byproduct); 
  72     for(i = 0; i < combines.size();) {
  73         for( j = i+1; j< combines.size() && combines[i].product == combines[j].product; j++)
  74             ;
  75         if(j == i+1)
  76             i++;
  77         else
  78             combines.erase(combines.begin()+i, combines.begin()+j);            
  79     }
  80 
  81     //remove combinations not consist with third clause
  82     sort(combines.begin(), combines.end(), bysum); 
  83     for(i = 0; i < combines.size();) {
  84         for( j = i+1; j< combines.size() && combines[i].sum == combines[j].sum; j++)
  85             ;
  86         if(j == i+1)
  87             i++;
  88         else
  89             combines.erase(combines.begin()+i, combines.begin()+j);
  90     }
  91     
  92     //output the result
  93     for(i = 0; i < combines.size(); i++) {
  94         cout << combines[i].x << " "<< combines[i].y <<" " <<combines[i].sum 
  95             <<" "<< combines[i].product<< endl;
  96     }
  97 }

Two_Numbers (2008-02-23 15:34:09由localhost编辑)

czk.8866.org | czk.3322.org | Copyright (c) 2006 czk. 浙ICP备06000584号