2013-06-18 09:01:14Morris
[UVA][循環] 11701 - Cantor
Problem C: Cantor
The ternary expansion of a number is that number written in base 3.
A number can have more than one ternary expansion. A ternary
expansion is indicated with a subscript 3.
For example, 1 = 13 = 0.222...3,
and 0.875 = 0.212121...3.
The Cantor set is defined as the real numbers between 0 and 1 inclusive that have a ternary expansion that does not contain a 1. If a number has more than one ternary expansion, it is enough for a single one to not contain a 1.
For example, 0 = 0.000...3 and 1 = 0.222...3, so they are in the Cantor set. But 0.875 = 0.212121...3 and this is its only ternary expansion, so it is not in the Cantor set.
Your task is to determine whether a given number is in the Cantor set.
Input Specification
The input consists of several test cases.Each test case consists of a single line containing a number x written in decimal notation, with 0 <= x <= 1, and having at most 6 digits after the decimal point.
The last line of input is END. This is not a test case.
Sample Input
0 1 0.875 END
Output Specification
For each test case, output MEMBER if x is in the Cantor set, and NON-MEMBER if x is not in the Cantor set.Output for Sample Input
MEMBER MEMBER NON-MEMBER
Malcolm Sharpe
題目要求三進制的浮點數表示法。並且判斷他是不是一個 Cantor set 的成員。
Cantor set 定義是不會出現 1 的數字。
根據二進制找浮點數表示法的方式，一直乘 3 就可以轉換了。
檢查到循環為止。
#include <stdio.h>
#include <set>
using namespace std;
int main() {
char s[105];
while(scanf("%s", s) == 1) {
if(s[0] == 'E') break;
int digit = 0, i;
int a = 0, b = 0, c = 1;
for(i = 0; s[i]; i++) {
if(s[i] == '.') {
for(i++; s[i]; i++, digit++)
b = b*10 + s[i]-'0', c = c*10;
break;
} else {
a = a*10 + s[i]-'0';
}
}
if((a == 1 && b == 0) || (a == 0 && b == 0)) {
puts("MEMBER");
continue;
}
set<int> R;
int NON = 0;
while(!NON) {
if(b*3/c == 1)
NON = 1;
b = (b*3)%c;
if(R.find(b) != R.end())
break;
R.insert(b);
}
if(!NON)
puts("MEMBER");
else
puts("NON-MEMBER");
}
return 0;
}