首页 > ACM题库 > HDU-杭电 > hdu 2714 ISBN[解题报告]other
2014
02-14

hdu 2714 ISBN[解题报告]other

ISBN

问题描述 :

Farmer John’s cows enjoy reading books, and FJ has discovered that his cows produce more milk when they read books of a somewhat intellectual nature. He decides to update the barn library to replace all of the cheap romance novels with textbooks on algorithms and mathematics. Unfortunately, a shipment of these new books has fallen in the mud and their ISBN numbers are now hard to read.

An ISBN (International Standard Book Number) is a ten digit code that uniquely identifies a book. The first nine digits represent the book and the last digit is used to make sure the ISBN is correct. To verify that an ISBN number is correct, you calculate a sum that is 10 times the first digit plus 9 times the second digit plus 8 times the third digit … all the way until you add 1 times the last digit. If the final number leaves no remainder when divided by 11, the code is a valid ISBN.

For example 0201103311 is a valid ISBN, since
10*0 + 9*2 + 8*0 + 7*1 + 6*1 + 5*0 + 4*3 + 3*3 + 2*1 + 1*1 = 55.

Each of the first nine digits can take a value between 0 and 9. Sometimes it is necessary to make the last digit equal to ten; this is done by writing the last digit as X. For example, 156881111X is a valid ISBN number.

Your task is to fill in the missing digit from a given ISBN number where the missing digit is represented as ‘?’.

输入:

* Line 1: A single line with a ten digit ISBN number that contains ‘?’ in a single position

输出:

* Line 1: A single line with a ten digit ISBN number that contains ‘?’ in a single position

样例输入:

15688?111X

样例输出:

1

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2714

题意:给一串ISBN号,根据算法求出缺的(?表示)那一位。算法是各位上的数字按权相加,和必须为11的倍数。

没啥好说的,直接穷举。注意不存在输出-1。

代码:

# include <stdio.h>
 
 
 int main ()
 {
     char str[20] ;
     int sum, i, pos ;
     while (gets(str))
     {
         sum = 0 ;
         for (i = 0 ; str[i] ; i++)
         {
             if (str[i] == '?') pos = i ;
             else if (str[i] == 'X') sum += 10 ;
             else sum += (10-i) * (str[i]-'0') ;
         }
         if (pos == 9)
         {
             if ((sum+10)%11==0) puts ("X") ;
             else{
                 for (i = 0 ; i <= 9 ; i++){
                     if ((sum + i)%11==0){ printf ("%d\n", i) ;
                     break ;}
                 }
             }
         }
         else
         {
             for (i =0 ; i <= 9 ; i++)
             {
                 if ((sum + (10-pos)*i)%11 == 0)
                 {
                     printf("%d\n", i) ;
                     break ;
                 }
             }
             if (i >=10) puts ("-1") ;
         }
     }
     return 0 ;
 }

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/06/10/2543846.html


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)