题解

70 条题解

  • 5
    @ 2017-08-02 14:29:10

    这题目有3点需要注意:1.当分数为3/1时要输出3;2.当连分数为[3;]时要输出[3];3.在分数转成连分数的时候不能使用浮点数,精度会出现问题,必须要用整数处理

    #include <bits/stdc++.h>
    using namespace std;
    
    int gcd(int x,int y)//求最大公约数
    {
        if(x<y) swap(x,y);
        int r=x%y;
        while(r){
            x=y;
            y=r;
            r=x%y;
        }
        return y;
    }
    int main()
    {
        //freopen("input.txt","r",stdin);
        string s;
        char c;
        while(getline(cin,s)){
            if(!isdigit(s[0])){//第一个不是数字即连分数,否则是分数
                int d;
                stack<int>ans;
                stringstream ss(s);
                ss>>c;
                while(ss>>d>>c) ans.push(d);//将连分数中的数字进栈
                int fz=1,fm=0;
                while(!ans.empty()){//将数字依次处理转换成分数
                    int x=ans.top();
                    ans.pop();
                    swap(fz,fm);
                    fz+=x*fm;
                }
                int gg=gcd(fz,fm);
                fz/=gg;fm/=gg;//约分为最简
                if(fm==1) printf("%d\n",fz);//考虑分母为1的情况,否则第4个点会报错
                else printf("%d/%d\n",fz,fm);
            }
            else{
                int fz,fm;
                queue<int>ans;
                stringstream ss(s);
                ss>>fz>>c>>fm;//提取分子和分母
                while(1){
                    /*
                    int tt=(int)t;
                    ans.push(tt);
                    t=t-tt;
                    if(fabs(t)<=1e-6) break;
                    t=1/t;
                    */
                    //在转换成连分数的时候不能用浮点数而要用整数,否则精度出现问题!!
                    int t=fz/fm;
                    ans.push(t);
                    fz=fz-t*fm;
                    if(fz==0) break;
                    swap(fz,fm);
                }
                if(ans.size()==1) {printf("[%d]",ans.front());continue;}//注意格式问题
                printf("[%d;",ans.front());
                ans.pop();
                while(ans.size()!=1){
                    printf("%d,",ans.front());
                    ans.pop();
                }
                printf("%d]\n",ans.front());
            }
        }
        return 0;
    }
    
    
  • 3
    @ 2017-11-10 00:24:45

    基于连分数的结构,可以采用链表的结构进行储存和处理

    连分数

    上图连分数即是[292;1,15,7,3]
    分解为[192;[1;[15;[7;[3;NULL]]]]]

    C
    若只是理解链表,看test()函数之上即可

    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct Ctnfrct {
        int base;
        struct Ctnfrct *next;
    } ctnfrct;
    typedef struct Frct {
        int up;
        int down;
    } frct;
    
    void swap(int *a, int *b) {
        int t = *a;
        *a = *b;
        *b = t;
    }
    
    void c2f(ctnfrct *ctn, frct *frc) {
        if (ctn->next) {
            c2f(ctn->next, frc);
            swap(&frc->down, &frc->up);
            frc->up = frc->down * ctn->base + frc->up;
        } else {
            frc->up = ctn->base;
            frc->down = 1;
        }
    }
    
    ctnfrct *f2c(frct frc) {
        ctnfrct *curr = (ctnfrct *) malloc(sizeof(ctnfrct));
        if (!frc.down) return (ctnfrct *) 0;
        if (frc.up != 1) {
            curr->base = frc.up / frc.down;
            frc.up %= frc.down;
            swap(&frc.up, &frc.down);
            curr->next = f2c(frc);
        } else {
            curr->base = frc.down;
            curr->next = (ctnfrct *) 0;
        }
        return curr;
    }
    
    //此函数与题无关,仅方便理解
    void test() {
        ctnfrct a = {3, (ctnfrct *) 0};
        ctnfrct b = {7, &a}, c = {15, &b}, d = {1, &c}, e = {292, &d};
        frct x;
        c2f(&e, &x);
    
        printf("%d/%d\n", x.up, x.down);
        x.up *= 2;
        x.down *= 2;
        ctnfrct *n = f2c(x);
        while (n) {
            printf("%d ", n->base);
            n = n->next;
        }
    }
    
    int main() {
        char str[1000], num_s[10];
        int num;
        while (scanf("%s", str) != EOF) {
            if (str[0] == '[') {
                ctnfrct head, *p = &head;
                int cnt = 0;
                for (int i = 1; i < strlen(str); i++) {
                    if (str[i] < '0' || str[i] > '9')
    
                    {
                        sscanf(num_s,"%d",&num);
                        ctnfrct *curr = (ctnfrct *) malloc(sizeof(ctnfrct));
    
                        curr->base = num;
                        curr->next = (ctnfrct *) 0;
                        p->next = curr;
                        p = p->next;
                        memset(num_s,0,sizeof(num_s));
                        cnt = 0;
                    } else {
                        num_s[cnt++] = str[i];
                    }
                }
                frct frc;
                c2f(head.next, &frc);
                if (frc.down != 1) printf("%d/%d\n", frc.up, frc.down);
                else printf("%d\n", frc.up);
            } else {
                frct frc;
                frc.down = 1;
                sscanf(str,"%d/%d",&frc.up,&frc.down);
                ctnfrct * ctn = f2c(frc);
                printf("[%d",ctn->base);
                if(ctn->next){
                    printf(";");
                    ctn = ctn->next;
                    while(ctn->next){
                        printf("%d,",ctn->base);
                        ctn = ctn->next;
                    }
                    printf("%d]\n",ctn->base);
                } else {
                    printf("]\n");
                }
    
            }
        }
    }
    
  • 2
    @ 2020-10-11 21:01:01

    主要注意的是将整数位和分数位分开的时候要判断一下是否存在,比如4测试点[2]应该输出2;2/1应该输出[2]而不是[2;]

    
    ```#!/usr/bin/env python
    # coding:utf-8
    """
    Name : main.py
    Author  : Tang
    """
    def fen2lian(fen: str) -> str:
        lian = '['
        a = int(fen.split('/')[0])
        b = int(fen.split('/')[1])
        lian += str(a // b)
        lian += ';'
        r = a % b
        a, b = b, r
        while r:
            lian += str(a // b)
            lian += ','
            r = a % b
            a, b = b, r
        lian = lian[:-1]
        lian += ']'
        return lian
    
    
    def lian2fen(lian: str) -> str:
        if ';' in lian:
            zheng = lian.split(';')[0][1:]
        else:
            return str(lian[1:-1])
        try:
            xiao = lian.split(';')[1].split(',')
            xiao[-1] = xiao[-1][:-1]
            b = int(xiao[-1])
            old_r = 1
            a = int(xiao[-2])
            new_r = b
            b = a * b + old_r
            old_r = new_r
            for i in range(len(xiao) - 2):
                try:
                    a = int(xiao[-3 - i])
                except IndexError:
                    break
                new_r = b
                b = a * b + old_r
                old_r = new_r
        except:
            b = int(lian.split(';')[1][:-1])
            new_r = 1
    
        A = int(zheng) * b + new_r
        return str(A) + "/" + str(b)
    
    
    if __name__ == '__main__':
        while True:
            try:
                s = input()
                if s[0] == '[':
                    print(lian2fen(s))
                else:
                    print(fen2lian(s))
            except EOFError:
                break
    
    
  • 2
    @ 2018-01-05 20:38:07

    python可以考虑用try-except来判断EOF

    import re
    
    
    def to_fraction(values):
        numerator = 1
        denominator = 0
        for x in reversed(values):
            numerator, denominator = denominator, numerator
            numerator += denominator * x
        return "%d/%d" % (numerator, denominator) if denominator > 1 else numerator
    
    
    def to_continued(numerator, denominator):
        res_str = "[%d;" % (numerator / denominator)
        numerator %= denominator
        if numerator == 0:
            return res_str.replace(";", "]")
        while numerator > 0:
            numerator, denominator = denominator, numerator
            res_str += "%d," % (numerator / denominator)
            numerator %= denominator
        return res_str.rstrip(",") + "]"
    
    
    while True:
        try:
            line = raw_input()
        except EOFError:
            break
        if line[0] == "[":
            print to_fraction(map(int, re.findall(r'\d+', line)))
        else:
            print to_continued(*map(int, re.findall(r'\d+', line)))
    
  • 2
    @ 2017-09-20 15:56:12

    字符串处理+模拟

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int maxn = 105;
    int a[maxn], len, x, y;
    char ch[1000];
    
    void swap(int& a,int& b){
        a=a^b, b=b^a, a=a^b;
    }
    int getin(){
        len=x=y=0;
        memset(a,0,sizeof(a));
        int lent=strlen(ch);
        if( ch[0]=='[' ){
            for ( int i=0; i<lent; i++ ){
                if( isdigit(ch[i]) ){
                    a[len]=a[len]*10+ch[i]-'0';
                }else len++;
            }
            len--;
            return 0;
        } else{
            for ( int i=0; i<lent; i++ ){
                if( isdigit(ch[i]) ){
                    x=x*10+ch[i]-'0';
                }else swap(x,y);
            }
            swap(x,y);
            return 1;
        }
    }
    int gcd(int x, int y){
        return y==0?x:gcd(y,x%y);
    }
    int main(){
        while( scanf("%s", ch)!=EOF ){
            if( getin() ){
                printf("[%d", x/y );
                x=x%y;
                if( x!=0 && y!=0 ) printf(";");
                swap(x,y);
                while( x!=1 && x!=0 && y!=0){
                    printf("%d",x/y);
                    x=x%y;
                    if( x==0 ) break;
                    swap(x,y);
                    if( x!=1 ) printf(",");
                }
                printf("]\n");
            }else {
                if( len>1 ){
                    x=1, y=a[len];
                    for ( int i=len-1; i>=1; i-- ){
                        x=y*a[i]+x;
                        if( i!=1 ) swap(x,y);
                    }
                    int d=gcd(x,y);
                    x/=d, y/=d;
                    if( y==0 ) printf("%d\n", x);
                    else printf("%d/%d\n",x/d,y/d);
                }else printf("%d\n", a[len] ); 
            }
        }
        return 0;
    }
    
  • 2
    @ 2009-11-08 10:10:12

    果然被恶心到了

    。。。。。。真的好恶心的题目

    很不讲道理的输入输出

    岛儿小过分了点

    给出几个猥琐的范例

    1/1 输出 【1】

    2/1 输出 【2】

    1 输出【1】

    2 输出【2】

    【1】 输出 1

    【2】 输出 2

    其他的应该没什么问题吧

    4/2 输出【2】

    就是这样了

    惨痛经历啊- -

  • 1
    @ 2020-02-05 14:32:40

    难点:
    1.未知行数
    2.约分
    3.特殊情况:
    n/1: [n]
    n: [n]
    连分数中数字不一定小于10
    然后就是算法:
    递归函数处理
    分数->连分数:基例-分母为1的时候直接输出分子;
    连分数->分数:基例-数组最后只剩分子和分母;
    递归链通过简单地推导很容易得出
    下面给出代码:

    #include<iostream>
    #include<string>
    #include<string.h>
    using namespace std;
    void reduction(int& a,int& b) {//约分
        int c = a < b ? a : b;
        int i;
        for (i = 2; i <= c; i++)if (a % i == 0 && b % i == 0) {
            a /= i;
            b /= i;
            reduction(a, b);
            break;
            }
    }
    void fraction(int num[], int n) {//连分数[数组]->分数
        if (n == 2) {
            reduction(num[0], num[1]);
            if (num[1] == 1)cout << num[0] << endl;
            else cout << num[0] << '/' << num[1] << endl;
        }
        else {
            num[n - 3] = num[n - 3] * num[n - 2] + num[n - 1];
            fraction(num, n - 1);
        }
    }
    void confrac(int a, int b) {//分数->连分数
        if (b == 1)cout << a << "]" << endl;
        else {
            cout << a / b << ",";
            int t;
            t = a;
            a = b;
            b = t % b;
            confrac(a, b);
        }
    }
    int main()
    {
        char x[100][256] = {'0'};
        for (int i = 0;cin>>x[i]; i++)
        {
            int num[100];
            if (x[i][0] == '[') {//连分数->分数
                int j = 0, k;
                num[0] = 0;
                for (k = 0;; k++)
                {
                    num[k] = 0;
                    for (; x[i][j] != ';' && x[i][j] != ','; j++) {
                        if (x[i][j] == ']')goto LOOP;
                        if (x[i][j] > 48 && x[i][j] <= 57)\
                            num[k] = 10 * num[k] + x[i][j] - 48;
                    }
                    j++;
                }
            LOOP:k++;num[k] = 1;k++;
                fraction(num, k);
            }
            else {//分数->连分数
                if (strstr(x[i], "/") == NULL)cout << "[" << atoi(x[i]) << "]" << endl;
                else {
                    int a, b, j;
                    a = atoi(x[i]);
                    string y;
                    y = string(x[i]);
                    for (j = 0; x[i][j] != '/'; j++);
                    y.replace(0, j + 1, "");
                    b = stoi(y, 0);
                    reduction(a, b);
                    if (b == 1)cout << "[" << a << "]" << endl;
                    else {
                        cout << "[" << a / b << ";";
                        int t;
                        t = a;
                        a = b;
                        b = t % b;
                        confrac(a, b);
                    }
                }
            }
        }
        return 0;
    }
    
  • 1
    @ 2017-04-30 15:12:39
    #include <iostream>
    #include <string>
    #include <memory.h>
    
    using namespace std;
    
    int main()
    {
        std::ios::sync_with_stdio(false);
        string s;
        while (cin >> s)
        {
            int a[100], t = 0;
            bool flag = false;
            memset(a, 0, sizeof(a));
            if (s[0] == '[')
            {
                for (int i = 1; i < s.size(); i++)
                {
                    if (s[i] >= '0'&&s[i] <= '9')
                    {
                        flag = true;
                        a[t] = a[t] * 10 + (int)(s[i] - '0');
                    }
                    else
                    {
                        t++;
                        flag = false;
                    }
                }
                int x = a[t], y = 1;
                for (int i = t; i >= 0; i--)
                {
                    int temp = x;
                    x = y + a[i] * x;
                    y = temp;
                }
                int max = x, min = y;
                while (max%min != 0)
                {
                    int temp = min;
                    min = max%min;
                    max = temp;
                }
                x = x / min, y = y / min;
                if (y == 1)
                    cout << x << endl;
                else
                    cout << x << "/" << y << endl;
            }
            else
            {
                for (int i = 0; i < s.size(); i++)
                {
                    if (s[i] >= '0'&&s[i] <= '9')
                    {
                        flag = true;
                        a[t] = a[t] * 10 + (int)(s[i] - '0');
                    }
                    else
                        t++;
                }
                if (t == 0)
                    cout << '[' << a[0] << ']' << endl;
                else
                {
                    int max = a[0], min = a[1];
                    while (max%min != 0)
                    {
                        int temp = min;
                        min = max%min;
                        max = temp;
                    }
                    int x = a[0] / min, y = a[1] / min;
                    t = 0;
                    cout << "[";
                    while (x != 1)
                    {
                        int div = x / y, rem = x%y;
                        if (t == 0)
                            cout << div;
                        else
                            if (t == 1)
                                cout << ";" << div;
                            else
                                cout << "," << div;
                        x = rem;
                        if (x != 1)
                        {
                            int temp = y;
                            y = x;
                            x = temp;
                        }
                        t++;
                    }
                    if (y != 0)
                        cout << ',' << y;
                    cout << ']' << endl;
                }
            }
        }
        return 0;
    }
    
    • @ 2017-07-27 21:10:04

      感谢大佬代码给的提示,要不我查错得查一晚上啊

  • 1
    @ 2017-01-26 18:13:47

    如果第四个测试数据过不了的话就是因为【4】-4/1;实际上应该是【4】-4;
    如果后三个没过的话可,就是你没有约分

  • 0
    @ 2019-12-23 21:02:23

    注意能整除的情况

    #include<iostream>
    #include<string.h>
    #include<string>
    #include<queue>
    using namespace std;
    queue<int>q;
    int gcd(int a,int b){
        if(a<b) swap(a,b);
        return b==0?a:gcd(b,a%b);
    }
    struct node{
        int x;
        int y;
        node(int a,int b){
            x=a;
            y=b;
        }
    };
    node operator+(node a,node b){
        int tx=a.x*b.y+b.x*a.y;
        int ty=a.y*b.y;
        int k=gcd(tx,ty);
        node c(tx/k,ty/k);
        return c;
    }
    node operator+(node a,int b){
        int tx=a.x+b*a.y;
        node c(tx,a.y);
        return c;
    }
    void cal1(char *a){
        int s=strlen(a),t=0,i=0;
        node ans(0,1);
        for(i=1;a[i]!=';'&&a[i]!=']';i++){
            t*=10;
            t+=a[i]-'0';
        }
        if(a[i]==0){
            cout<<t<<endl;
            return;
        }
        ans.x=t;
        i++;
        int u=i;
        node tn(0,1);
        for(i=s-2;i>=u;i--){
            tn=tn+(a[i]-'0');
            swap(tn.x,tn.y);
            if(a[i-1]==',') i--;
        }
        ans=ans+tn;
        if(ans.y==1) cout<<ans.x<<endl;
        else cout<<ans.x<<'/'<<ans.y<<endl;
    }
    void cal2(char *a){
        int tx=0,ty=0,i=0,s=strlen(a);
        for(i=0;a[i]!='/'&&a[i]!=0;i++){
            tx*=10;
            tx+=a[i]-'0';
        }
        if(s==i+1){
            cout<<'['<<tx<<']'<<endl;
            return;
        }
        i++;
        for(i;a[i]!=0;i++){
            ty*=10;
            ty+=a[i]-'0';
        }
        int tt=gcd(tx,ty);
        tx=tx/tt;
        ty=ty/tt;
        if(ty==1){
            cout<<'['<<tx<<']'<<endl;
            return;
        }
        cout<<'['<<tx/ty<<';';
        tx=tx%ty;
        swap(tx,ty);
        while(!q.empty()) q.pop();
        while(1){
            tt=gcd(tx,ty);
            tx=tx/tt;
            ty=ty/tt;
            q.push(tx/ty);
            tx=tx%ty;
            swap(tx,ty);
            if(tx%ty==0){
                q.push(tx/ty);
                break;
            }
        }
        while(!q.empty()){
            cout<<q.front();
            q.pop();
            if(!q.empty()) cout<<',';
        }
        cout<<']'<<endl;
    }
    int main(){
        char a[1000];
        while(cin>>a){
        if(a[0]=='['){
            cal1(a);
        }
        else{
            cal2(a);
        }
        }
    }
    
    
  • 0
    @ 2019-11-20 11:12:05

    #include<iostream>//不会压行的蒟蒻
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int F[120];
    char A[10000];
    int main()
    {
    while(scanf("%s",A) != EOF){
    if(A[0] == '['){
    int I = 0;
    int cursor = 0;
    for(int i = 1 ; i < strlen(A) ; i++){
    if(A[i] >= '0' && A[i] <= '9'){
    I = 10*I + A[i] - '0';
    }
    if((A[i] == ';' || A[i] == ',' || A[i] == ']') && A[i - 1] >= '0' && A[i - 1] <= '9'){//;是连分数的第一段整数。连分数可能没有后面的分数段
    F[cursor++] = I;//F[0]是整数段
    I = 0;
    }
    }
    I = F[0];//整数部分
    if(cursor == 1)//只有第一段的整数
    cout<<F[0]<<endl;
    else{
    int a = 1,b = F[--cursor];//a/b是分数部分
    if(cursor > 1){
    while(cursor> 1){
    int tmp = b;
    b = F[cursor - 1] * b + a;
    a = tmp;
    cursor--;
    }
    }
    I *= b;

    int j = __gcd(I + a, b);//约分
    cout<<I+a/j<<"/"<<b/j<<endl;
    }
    }

    else{
    int I = 0;
    int a = 0, b = 0;
    bool flag = false;
    for(int i = 0 ; i < strlen(A) ; i++){//a/b字符串对应的分子分母
    if(A[i] == '/'){
    flag = true;// ‘/’前的分子。分母未必有
    if(A[0] == '-')
    a = -a;
    continue;
    }
    if(flag == false && A[i] >= '0' && A[i] <= '9')
    a = 10*a + A[i] - '0';
    else if(flag == true && A[i] >= '0' && A[i] <= '9')
    b = 10*b + A[i] - '0';
    }
    if(flag == true){//分数形式,但可能分子分母整除了
    cout<<"["<<a/b;
    if(a%b == 0){//整除关系
    cout<<"]"<<endl;
    continue;
    }
    else{
    cout<<";";//整数部分完成
    while(1){
    a %= b;
    cout<<b/a;
    swap(a, b);
    if(a%b != 0)
    cout<<",";
    else{//整除即最后一段
    cout<<"]"<<endl;
    break;
    }
    }
    }
    }
    else{//整数形式
    cout<<"["<<a<<"]"<<endl;
    }
    }
    }
    return 0;
    }

  • 0
    @ 2017-08-15 10:38:32

    借鉴了之前的同学的代码;有一点点的改动([2;] -> [2]),我借鉴的那个代码输出了[2;]实际应该输出[2];
    #include<vector>
    #include<cstdio>
    using namespace std;

    int gcd(int x, int y){
    int tmp;
    tmp = x%y;
    while(tmp != 0){
    x = y;
    y = tmp;
    tmp = x%y;
    }
    return y;
    }
    struct Frac{
    int x, y;
    Frac(int a){
    x = a;
    y = 1;
    }
    Frac(int a, int b){
    if(a != 0){
    int m = gcd(a, b);
    a /= m;
    b /= m;
    x = a;
    y = b;
    }else{
    x = 0;
    y = 1;
    }
    }
    void operator += (const Frac &r){
    int x0 = x*r.y + y*r.x;
    int y0 = y*r.y;
    int m = gcd(x0, y0);
    x0 /= m;
    y0 /= m;
    x = x0;
    y = y0;
    }
    void filp(){
    int m = x;
    x = y;
    y = m;
    }
    void print(){
    if(y == 1){
    printf("%d\n", x);
    }else{
    printf("%d/%d\n", x, y);
    }
    }
    };
    char s[100000];
    int main(){
    while(scanf("%s", s) == 1){
    if(s[0] == '['){
    vector<int> a;
    int i;
    for(i = 1; s[i] != 0; ++i){
    if(s[i] >= '0' && s[i] <= '9'){
    int x = 0;
    while(s[i] >= '0' && s[i] <= '9'){
    x = x*10 + s[i] - '0';
    ++i;
    }
    --i;
    a.push_back(x);
    }
    }
    Frac f(0);
    for(int i = a.size() - 1; i >= 0; --i){
    f += Frac(a[i]);
    if(i){
    f.filp();
    }
    }
    f.print();
    }else{
    int x, y;
    vector<int> a;
    sscanf(s, "%d/%d", &x, &y);
    Frac f(x, y);
    while(f.y != 1){
    a.push_back(f.x/f.y);
    f.x %= f.y;
    f.filp();
    }
    a.push_back(f.x);
    if(a.size() == 1){
    printf("[%d]\n", a[0]);

    }else{
    printf("[");
    for(int i = 0; i < a.size(); ++i){
    printf("%d", a[i]);
    if(i == 0){
    printf(";");
    }else{
    if(i != a.size() - 1){
    printf(",");
    }
    }
    }
    printf("]\n");
    }

    }
    }
    return 0;
    }

  • 0
    @ 2017-08-14 13:40:07
    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    long a[1000];
    void aha1(int x,int y,int t)
    {
        for(int i=t;i>=1;i--)
        {
            long c=x;
            x=y;
            y=c;
            x=x+y*a[i];
        }
        printf("%ld",x);
        if(y!=1)
            printf("/%ld",y);
        printf("\n");
        return;
    }
    void aha2(int x,int y)
    {
        long e=1,k;
        k=x/y;
        printf("[%ld",k);
        x=x-k*y;
        while(x!=0)
        {
            int c=x;
            x=y;
            y=c;
            k=x/y;
            x=x-k*y;
            if(e==1)
                printf(";%ld",k),e=0;
            else
                printf(",%ld",k);
        }
        printf("]\n");
    }
    int main(){
        char x[1000];
        while(gets(x))
        {
            memset(a, 0, sizeof(a));
            if(x[0]=='[')
            {
                int t=1,q=1;
                while(x[q]!=']')
                {
                    if(x[q]>='0'&&x[q]<='9')
                    {
                        a[t]=a[t]*10+x[q]-'0';
                    }
                    else
                        t++;
                    q++;
                }
                aha1(a[t],1,t-1);
            }
            else
            {
                int t=1,q=0;
                while(x[q]!='\n'&&x[q]!=EOF&&x[q]!='\0')
                {
                    if(x[q]>='0'&&x[q]<='9')
                    {
                        a[t]=a[t]*10+x[q]-'0';
                    }
                    else
                        t++;
                    q++;
                }
                int m=a[1],n=a[2];
                aha2(m,n);
            }
        }
        return 0;
    }
    
  • 0
    @ 2017-07-12 01:41:24
    //可能比较方便理解?
    #include <iostream>
    #include <string>
    #include <cmath>
    #include <vector>
    
    using namespace std;
    
    vector<int> f2c(long p, long q) {
        vector<int> ret;
        ret.push_back((int)(p / q));
        if (p%q) {
            vector<int> tmp = f2c(q, p%q);
            ret.insert(ret.end(), tmp.begin(), tmp.end());
        }
        return ret;
    }
    
    void c2f(vector<int> c, long *p, long *q) { // 1/p/q
        if (c.size() == 1) {
            *p = 1; *q = c[0];
        } else {
            long np = 0, nq = 0;
            vector<int> tmp;
            tmp.insert(tmp.end(), c.begin() + 1, c.end());
            c2f(tmp, &np, &nq);
            *p = nq;
            *q = nq*c[0] + np;
        }
    }
    
    int main(void) {
        string input;
        while (cin >> input) {
            if (input[0] == '[') {
                string pure = input.substr(1, input.length() - 2) + ',';
                for (int i = 0; i < input.length(); i++)
                    if (pure[i] == ';')
                        if(pure[i+1]==',')
                            pure.at(i) = ' ';
                        else
                            pure.at(i) = ',';
    
                vector<int> t;
                size_t pos = pure.find(',');
                size_t size = pure.size();
    
                while (pos != string::npos) {
                    string x = pure.substr(0, pos);
                    t.push_back(atoi(x.c_str()));
                    pure = pure.substr(pos + 1, size);
                    pos = pure.find(',');
                }
                
                long p, q;
                c2f(t, &p, &q);
                //cout << q << '/' << p << endl;
                if (p != 1)
                    cout << q << '/' << p << endl;
                else
                    cout << q << endl;
    
                
            } else {
                string s1, s2;
                auto it = input.find('/');
                if (it > input.size()) {
                    s1 = input; s2 = "0";
                } else {
                    s1 = input.substr(0, it);
                    s2 = input.substr(it + 1, input.length() - it);
                }
                long p, q;
                p = atoi(s1.c_str());
                q = atoi(s2.c_str());
                vector<int> C = f2c(p, q);
                cout << "[" << C[0] << ";";
                for (int i = 1; i < C.size(); i++) {
                    cout << C[i];
                    if (i != C.size() - 1)
                        cout << ",";
                }
                cout << "]" << endl;
            }
        }
        return 0;
    }
    
  • 0
    @ 2016-08-26 13:26:12

    评测结果
    编译成功

    Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
    Copyright (c) 1993-2015 by Florian Klaempfl and others
    Target OS: Win32 for i386
    Compiling foo.pas
    Linking foo.exe
    62 lines compiled, 0.0 sec, 28352 bytes code, 1268 bytes data
    测试数据 #0: Accepted, time = 0 ms, mem = 1272 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 1272 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 1308 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 1272 KiB, score = 20
    测试数据 #4: Accepted, time = 15 ms, mem = 1236 KiB, score = 20
    Accepted, time = 15 ms, mem = 1308 KiB, score = 100
    代码
    program p1696;
    var
    a:ansistring;
    b:array[1..100000]of longint;
    i,n,j,k,num1,num2,x,t:longint;
    function pd(n:longint):boolean;
    begin
    if n in [48..57] then pd:=false else pd:=true;
    end;
    begin
    while not eof do begin
    readln(a);
    n:=length(a);
    if pd(ord(a[1])) then begin
    i:=2;x:=0;j:=1;num1:=1;
    while i<n do
    begin
    repeat
    x:=x*10+(ord(a[i])-ord('0'));
    inc(i);
    until (pd(ord(a[i]))) or (i>n);
    inc(i);
    b[j]:=x;
    x:=0;
    inc(j);
    end;
    dec(j);
    if j=1 then writeln(b[1]) else begin
    num2:=b[j];
    for k:=j downto 1 do
    begin
    num1:=b[k-1]*num2+num1;
    t:=num1; num1:=num2; num2:=t;
    end;
    writeln(num1,'/',num2);
    end;
    end else begin
    i:=1;x:=0;j:=0;num1:=0;num2:=0;
    while i<=n do
    begin
    repeat
    x:=x*10+(ord(a[i])-ord('0'));
    inc(i);
    until (pd(ord(a[i]))) or (i>n);
    inc(i);
    if j=0 then begin num1:=num1+x; inc(j); x:=0;
    end else num2:=num2+x;
    end;
    if num2=0 then writeln('[',num1,']')else
    if num1 mod num2=0 then writeln('[',num1 div num2,']')
    else begin
    write('[');
    for k:=1 to 1000 do begin
    b[k]:=num1 div num2;
    num1:=num1 mod num2;
    t:=num1; num1:=num2; num2:=t;
    if k=1 then write(b[k],';')
    else if num2<1 then begin writeln(b[k],']');break;end else write(b[k],',');
    end;
    end;
    end;
    end;
    end.

  • 0
    @ 2016-03-08 13:41:26

    测试数据 #0: Accepted, time = 0 ms, mem = 796 KiB, score = 20
    测试数据 #1: Accepted, time = 0 ms, mem = 800 KiB, score = 20
    测试数据 #2: Accepted, time = 0 ms, mem = 800 KiB, score = 20
    测试数据 #3: Accepted, time = 0 ms, mem = 800 KiB, score = 20
    测试数据 #4: Accepted, time = 15 ms, mem = 800 KiB, score = 20
    第四个数据原本老是错,暴力模拟就可以AC了,感觉程序好长

  • 0
    @ 2009-11-08 07:58:03

    测试数据04 应该是

    2/1

    [2]

    之类的数据吧

    输出是

    [2]

    2

  • -1
    @ 2017-06-12 15:23:35
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<sstream>
    #include<string>
    #include<algorithm>
    #include<numeric>
    #include<vector>
    using namespace std;
    
    int p[200] = { 0 };
    int q[200] = { 0 };
    int fra[200] = { 0 };
    int gcd(int a, int b)
    {
        if (a < b)
        {
            int temp;
            temp = a;
            a = b;
            b = temp;
        }
        while (a%b)
        {
            int re = 0;
            re = a%b;
            a = b;
            b = re;
            re = a%b;
        }
        return b;
    }
    void fraction_to_num(string fraction)
    {
        int nume = 0;
        int deno = 0;
        int re = 0;
        int quo = 0;
        int i = 0;
    
        string s1, s2;
        string s3;
        size_t it;
        stringstream str1,str2;
        stringstream str3;
    
        it = fraction.find('/');
        if (it > fraction.size()){
            s1 = fraction; s2 = "0";
        }
        else
        {
            s1 = fraction.substr(0, it);
            s2 = fraction.substr(it + 1, fraction.length() - it);
        }
        
    
        str1 << s1;
        str2 << s2;
    
        str1 >> nume;
        str2 >> deno;
    
    
        if (nume >= deno)
        {
            if (deno != 0)
            {
                while ((nume / deno) != 0)
                {
                    quo = nume / deno;
                    re = nume%deno;
                    fra[i++] = quo;
                    if (re == 0)break;
                    nume = deno;
                    deno = re;
                }
            }
            else
            {
                fra[i++] = nume;
            }
            
            str3 << "[";
            for (int k = 0; k < i; k++)
            {
                str3 << fra[k];
                if (k <= (i - 2))
                {
                    if (k == 0)str3 << ";";
                    else str3 << ",";
                }
            }
            str3 << "]";
            str3 >> s3;
        }
        else
        {
            int temp;
            temp = nume;
            nume = deno;
            deno = temp;
            while ((nume / deno) != 0)
            {
                quo = nume / deno;
                re = nume%deno;
                fra[i++] = quo;
                if (re == 0)break;
                nume = deno;
                deno = re;
            }
            str3 << "[0;";
            for (int k = 0; k < i; k++)
            {
                str3 << fra[k];
                if (k <= (i - 2))
                {
                     str3 << ",";
                }
            }
            str3 << "]";
            str3 >> s3;
        }
        cout << s3<<endl;       
    }
    void num_to_fraction(string s)
    {
        string num;
        int i = 0;
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '[' || s[i] == ']' || s[i] == ';' || s[i] == ',')
                continue;
            num.push_back(s[i]);
        }
        if (num.size() >= 2)
        {
            
            for (i = 0; i < num.length(); i++)
            {
                if (i == 0)
                {
                    p[0] = num[0] - '0';
                    q[0] = 1;
                }
                else
                if (i == 1)
                {
                    p[1] = (num[0] - '0')*(num[1] - '0') + 1;
                    q[1] = (num[1] - '0');
                }
                else
                {
                    p[i] = (num[i] - '0')*p[i - 1] + p[i - 2];
                    q[i] = (num[i] - '0')*q[i - 1] + q[i - 2];
                }
            }
            cout << p[i - 1] / gcd(p[i - 1], q[i - 1]) << "/" << q[i - 1] / gcd(p[i - 1], q[i - 1]) << endl;
        }
        else
        {
            cout << num << endl;
        }
        
    }
    
    
    int main()
    {
        //freopen("data.in", "r", stdin);
        //freopen("data.out", "w", stdout);
        string t;
    
        while (cin >> t)
        {
            if (t[0] == '[')
            {
                num_to_fraction(t);
            }
            else
            {
                fraction_to_num(t);
            }
        }
        return 0;
    }
    
    
  • -1
    @ 2017-05-19 10:01:12
    #include<string.h>
    #include<stdio.h>
    #include<ctype.h>
    #include<math.h>
    #define MAX 100
    //声明全局变量
    char s[MAX];
    int store[MAX];
    int m, n;
    int *mu = &m, *zi = &n;
    //函数swap,用于交换分子分母
    void swap(int *a, int *b)
    {
        int t;
        t = *a;
        *a = *b;
        *b = t;
    }
    //函数add,取倒数后相加并约分
    void add(int *a, int *b, int x)//*a是分子,*b是分母,分子小于分母
    {
        *a += (*b)*x;            //相加
        for (int i = *a; i >= 1; i--)   //找到最大公因数,约分
            if (*b%i == 0 && *a / i == 0)
            {
                *b /= i;
                *a /= i;
                break;
            }
        swap(a, b);              //调换分子分母的位置
    }
    //函数lianTofen,用于将连分数形式[n;a,b,…]转换为分数形式x/y
    void lianTofen(char *s)
    {
        int len = strlen(s);
        int i, num = 0;
        int j = 0;
        for (i = 1; i < len; i++)        //连分数表示法中第一个元素是[,故从下标1开始
        {                                //注意到s[len-1]是],s[len-2]一定是一个数字
            if (isdigit(s[i]))
            {
                num = num * 10 + (s[i] - '0');
                store[j] = num;          //store[]用来存储s[]中的数值的
            }
            else {
                num = 0;
                j++;
            }
        }
        store[j] = 1;                    //运算
        *zi = store[j], *mu = store[j - 1];
        for (i = j - 1; i >= 1; i--)
        {
            add(zi, mu, store[i - 1]);
    
        }
        swap(zi, mu);
    }
    //函数fenTolian,把分数形式转换为连分数形式并输出
    void fenTolian(char *s)
    {
        int len = strlen(s);
        int a = 0, b = 0;
        int i, k = 0, j = 0;
        for (i = 0; i < len; i++)
            if (!isdigit(s[i]))
                k = i;               //找到'/'在数组中的下标k
        for (i = 0; i < k; i++)
            a = 10 * a + s[i] - '0';
        for (i = k + 1; i < len; i++)
            b = 10 * b + s[i] - '0';
        do {
            k = a / b;               //取整
            store[j++] = k;
            a = a - k*b;
            if (a == 0)break;
            swap(&a, &b);
        } while (1);
        if (j == 1)
            printf("[%d]\n", store[0]);
        else
        {
            printf("[%d;", store[0]);
            printf("%d", store[1]);
            for (i = 2; i < j; i++)
                printf(",%d", store[i]);
            printf("]\n");
        }
    }
    int main()
    {
        while (scanf("%s",s)>0)
        {
            if (s[0] == '[')
            {
                lianTofen(s);
                if(m!=1)                      //要考虑分母是1的情况
                {
                    printf("%d/%d\n", n, m);  //注意这里的分母和分子是调换的
                }
                else printf("%d\n", n);
            }
            else
                fenTolian(s);
        }
        return 0;
    }
    
    
  • -1
    @ 2017-05-02 19:54:56

    强烈要求改描述,反正我想不到最后输出的**不是分数**= =

    #include <bits/stdc++.h>
    using namespace std;
    
    char s[100000];
    
    struct Frac {
        int upper,downer;
        Frac()
        {
        }
        Frac(int x)
        {
            upper=x;downer=1;
        }
        Frac(int x,int y)
        {
            if (!x) {
                upper=0;downer=1;
            } else {
                int g=__gcd(x,y);
                x/=g;y/=g;
                upper=x;downer=y;
            }
        }
        Frac operator +(const Frac &r)
        {
            return Frac(upper*r.downer+r.upper*downer,downer*r.downer);
        }
        void flip()
        {
            swap(upper,downer);
        }
        void print()
        {
            if (downer==1) {
                printf("%d\n",upper);
            } else {
                printf("%d/%d\n",upper,downer);
            }
        }
    };
    
    int main()
    {
        while (scanf("%s",s)!=EOF) {
            if (s[0]=='[') {
                vector<int> a;
                for (int i=1;s[i];i++) {
                    if ('0'<=s[i]&&s[i]<='9') {
                        int x=0;
                        while ('0'<=s[i]&&s[i]<='9') x=x*10+s[i++]-'0';
                        a.push_back(x);
                    }
                }
                Frac t(0);
                for (int i=a.size()-1;i>=0;i--) {
                    t=t+Frac(a[i]);
                    if (i) t.flip();
                }
                t.print();
            } else {
                int x,y;
                sscanf(s,"%d/%d",&x,&y);
                Frac t(x,y);
                vector<int> ans;
                while (t.downer!=1) {
                    ans.push_back(t.upper/t.downer);
                    t.upper%=t.downer;
                    t.flip();
                }
                ans.push_back(t.upper);
                putchar('[');
                for (int i=0;i<ans.size();i++) {
                    printf("%d",ans[i]);
                    if (i==0) putchar(';');
                    else if (i!=ans.size()-1) putchar(',');
                }
                puts("]");
            }
        }
        return 0;
    }
    

信息

ID
1696
难度
7
分类
其他 | 数学模拟 点击显示
标签
递交数
5070
已通过
1112
通过率
22%
被复制
2
上传者