紫书 2019.10.9

发表于 | 评论数： | 阅读次数：

紫书习题3道 2019.10.9

无话可说，紫书不愧是你

我是真的布吉岛这个玩意咋写，就先这么呆着吧QAQ。

no.1 uva202

就是寻找循环节，在除法计算的过程中判断一个循环节是否出现，而循环节的第二次出现意味着计算过程中的余数出现了第二次。举例1/3，商是0（在c语言里），代表这个除法的整数部分是0，余数是1，再乘10，得到的10作为第一步的分子，10/3的商是3，代表这个除法的第一位小数是3，余数是1，然后接下来也是这种步骤。

可以发现每步的除法只跟分子有关，也就是当分子出现重复值，便出现了循环节。

在程序的实现过程中，可以不用存储余数的值，只用存储分子和商，定义了二维数组，s[0] [i]存储第i步的分子，s[1] [i]存储第i步的商

Bjyx()用来找i位之前是否有重复分子出现，有则返回周期len

之后就是基操enmmmm，需要注意的是分子的计算用s[0] [q] = (A[0] [q-1] - b A[1] [q-1])10 ;这样可以避免a/b = 0，从而不使用%来取得余数

然后注意输出格式，不然会pe

还xiao习到了可以用巢鸽原理（抽屉原理,狄利克雷原则）：

简单的描述：如果有n个笼子，n+1只鸽子居住，则至少有一个笼子有两只鸽子。

一般化的描述（用高斯函数来叙述）：将n个元素分到m个集合中，至少有一个集合中元素个数大于等于[(n-1)/m]+1 。

对于本题，a%b最多有b-1个情况，根据巢鸽原理，循环节数小于等于b-1.

还可以考虑一下用gcd对分数化简

（大概没什么好说的了吧23333）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 2005 ;
int s[2][maxn] ;
int a , b , i , len , p , q ;

int Bjyx()
{
    for(p = 1 ; p < q ; ++p)
    {
        if(s[0][p] == s[0][q])
            return q - p ;
    }
    return -1 ;
}

int main()
{
    while(cin >> a >> b)
    {
        s[0][0] = a ;
        s[1][0] = a / b ;
        for(q = 1 ; ; ++q)
        {
            s[0][q] = (s[0][q - 1] - b * s[1][q - 1]) * 10 ;
            s[1][q] = s[0][q] / b ; 
            len = Bjyx() ;
            if(len > 0)
                break ;
        }
        printf("%d/%d = %d.", a , b , s[1][0]) ;
        for(int i = 1; i < p; ++i)
        {
            printf("%d", s[1][i]) ;
        }
        printf("(") ;
        for(int i = p ; i < q ; ++i)
        {
            if(i > 50)
            {
                printf("...") ;
                break ;
            }
            printf("%d", s[1][i]) ;
        }
        printf(")\n   %d = number of digits in repeating cycle\n\n" ,  len) ;
    }
    return 0;
}

no.2 uva1588

enmmm大概就是求新长条的最长的长度

可以先将一个长条a固定，将另外一个长条b依次后移，b移动不了就以b为基准固定，然后移动a。

由题可知，长条不能被翻转或者是旋转，所以只能从左往右移动，并且不用将长条逆置，这样的话只用扫描两次就可以了。

这道题主要是控制边界，例如i + j < lena，要不然最大长度会比正常的长一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1e5 + 5 ;
int main()
{
    char sa[maxn] , sb[maxn] ;
    while(cin >> sa >> sb)
    {
        int i ;
        int a[maxn] , b [maxn] ;
        int lena = strlen(sa) ;
        int lenb = strlen(sb) ;
        for(i = 0 ; i < lena; ++i)
        {
            a[i] = sa[i] - '0' ;
        }
        for(i = 0 ; i < lenb ; ++i)
        {
            b[i] = sb[i] - '0' ;
        }
        for(i = 0 ; i < lena ; ++i)
        {
            int flag = 1 ;
            for(int j = 0 ; j < lenb && i + j < lena ; ++j) // 注意处理边界问题
            {
                if(a[i + j] + b[j] == 4)
                {
                    flag = 0 ;
                    break ;
                }
            }
            if(flag == 1)
                break ;
        }
		int ans1 = max(lena , lenb + i) ;
        for(i = 0 ; i < lenb ; ++ i)
        {
            int flag = 1 ;
            for(int j = 0 ; j < lena && i + j < lenb ; ++j)
            {
                if(a[j] + b[i + j] == 4)
                {
                    flag = 0 ;
                    break ;
                }
            }
            if(flag == 1)
                break ;
        }
		int ans2 = max(lena + i , lenb) ;
		int minn = min(ans1 , ans2) ;
		cout << minn << endl ;
    }
    return 0 ;
}

no.3 uva 11809

。。。这题我绝对踩着时间过得。。。忽然好奇输入是个什么妖魔鬼怪。

有题目可得公式

之后由于数字过大无法存储，所以对等式两边同时求以10为底的对数，则公式可以化为

这道题还是要注意精度的。double，float对于逻辑运算符 == 基本无用。两数是否相等，应采用如fabs(a-b)<eps的方式，这道题中eps我取的1e-6,但是1e-5,1e-4应该都阔以。

我还是好奇if(a == 0 && b == 0)那个放到下面为啥就过了，好奇数据.jpg.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const double eps = 1e-5;
int main()
{
    double a , b , m , n ;
    while(scanf("%17lfe%lf" , &a , &b) != EOF)
    {
        if(a == 0 && b == 0)
            break ;
        int flag = 0 ;
        for(int i = 0 ; i < 10 ; ++ i)
        {
            for(int j = 1 ; j < 31 ; ++ j)
            {
                m = 0.0 ;
                n = 0.0 ;
                for(int x = 1 ; x < i + 2 ; ++ x)
                {
                    m ++ ;
                    m /= 2 ;
                }
                for(int y = 1 ; y < j + 1 ; ++ y)
                {
                    n *= 2 ;
                    n ++ ;
                }
                if(abs((log(a) + b * log(10)) - (log(m) + n * log(2))) < eps)
                {
                    printf("%d %d\n" , i , j) ;
                    flag = 1 ;
                    break ;
                }
            }
            if(flag == 1)
                break ;
        }
    }
    return 0 ;
}

弱小孤独无助又能吃.jpg

委屈巴巴.jpg

------------这篇文章结束了呢要不要夸夸我呢-------------