想吃冰卻又敏感保護不足?來自星星的你也會打廣告?輕忽小中風,當心變殘障黃曉明、林志玲攜手代言...
2012-04-19 07:24:36 人氣(619) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 263 - Number Chains

0
收藏
0
推薦


 Number Chains 

Given a number, we can form a number chain by

arranging its digits in descending order
arranging its digits in ascending order
subtracting the number obtained in (2) from the number obtained (1) to form a new number
and repeat these steps unless the new number has already appeared in the chain

Note that 0 is a permitted digit. The number of distinct numbers in the chain is the length of the chain. You are to write a program that reads numbers and outputs the number chain and the length of that chain for each number read.

Input and Output

The input consists of a sequence of positive numbers, all less than tex2html_wrap_inline27 , each on its own line, terminated by 0. The input file contains at most 5000 numbers.

The output consists of the number chains generated by the input numbers, followed by their lengths exactly in the format indicated below. After each number chain and chain length, including the last one, there should be a blank line. No chain will contain more than 1000 distinct numbers.

Sample Input

123456789
1234
444
0

Sample Output

Original number was 123456789
987654321 - 123456789 = 864197532
987654321 - 123456789 = 864197532
Chain length 2

Original number was 1234
4321 - 1234 = 3087
8730 - 378 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length 4

Original number was 444
444 - 444 = 0
0 - 0 = 0
Chain length 2


做法 : 模擬題

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
using namespace std;
int cmp1(const void *i, const void *j) {
    return *(char *)i - *(char *)j;
}
int cmp2(const void *i, const void *j) {
    return *(char *)j - *(char *)i;
}
int main() {
    int n;
    while(scanf("%d", &n) == 1 && n) {
        char des[20], asc[20];
        sprintf(des, "%d", n);
        sprintf(asc, "%d", n);
        int x, y, chain = 0;
        map<int, int> record;
        printf("Original number was %d\n", n);
        record[n] = 1;
        while(true) {
            chain++;
            qsort(des, strlen(des), sizeof(char), cmp1);
            qsort(asc, strlen(asc), sizeof(char), cmp2);
            sscanf(asc, "%d", &x);
            sscanf(des, "%d", &y);
            n = x - y;
            printf("%d - %d = %d\n", x, y, n);
            if(record[n] == 1)
                break;
            record[n] = 1;
            sprintf(des, "%d", n);
            sprintf(asc, "%d", n);
        }
        printf("Chain length %d\n\n", chain);
    }
    return 0;
}


263Number Chains
台長:Morris
人氣(619) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][EASY] 12403 - Save Setu
此分類上一篇:[UVA][AC自動機] 10679 - I Love Strings!!

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文