输出格式按讨论调整了,第4个点还是WA。。。

链表表示连分数,输出格式已经做到了 [2/1] —> 2, [2] —> 2, [2;] —> 2, 2/1 —> [2], 2 —> [2] 等等,还是不行。。。调试已疯,跪求大神指点!

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

struct num {
    int n;
    num *next;
};

typedef struct num num;

int suc_div(int, int);  // successive division to get the G.C.D.
void addnode(num **, int); // add node to the linked list
int * frac_add(int, num*); // add for a1 + 1 / a2, along the linked list
num * com2cont(int , int); // transform common fraction to continued fraction
int * cont2com(num *); // transform continued fractoin to common fraction
void cont_out(num *); // output continued fraction

int main()
{
    char in[1000000];
    while (!feof(stdin))
    {
        cin >> in;
        if (in[0] == '[')   // continued fraction -> common fraction
        {
            num *cont = NULL;
            char *pch = strtok(in, "[;,]");
            while (pch)
            {
                addnode(&cont, atoi(pch));
                pch = strtok(NULL, "[;,]");
            }
            int *tmp = cont2com(cont);
            if (tmp[1] == 1)
                cout << tmp[0] << endl;
            else
                cout << tmp[0] << '/' << tmp[1] << endl;
        }
        else    // common fraction -> continued fraction
        {
            int numer, denom, gcd;
            num *cont = NULL;
            char *pch;
            pch = strtok(in, "/");
            numer = atoi(pch);
            pch = strtok(NULL, "/");
            if (numer == 0)
                cout << "[0]" << endl;
            else
            {
                if (pch)    // in case the input is an integer
                {
                    denom = atoi(pch);
                    gcd = suc_div(numer, denom);
                    numer = numer / gcd;
                    denom = denom / gcd;
                    cont = com2cont(numer, denom);
                    cont_out(cont);
                }
                else
                    cout << '[' << numer << ']' << endl;
            }
        }
    }

    return 0;
}

int suc_div(int a, int b)
{
    int div, res;
    if (a > b)
    {
        div = b;
        res = a % b;
    }
    else
    {
        div = a;
        res = b % a;
    }
    while (res != 0)
    {
        int tmp = res;
        res = div % res;
        div = tmp;
    }
    return div;
}

void addnode(num **l, int d)
{
    num *new_node;
    new_node = (num *)malloc(sizeof *new_node);
    new_node->n = d;
    new_node->next = NULL;
    if (*l == NULL)
        *l = new_node;
    else
    {
        num *pointer = *l;
        while (pointer->next != NULL)
            pointer = pointer->next;
        pointer->next = new_node;
    }
}

int * frac_add(int a, num *l)
{
    int *tmp;
    tmp = (int *)malloc(2 * sizeof(int));
    if (l->next == NULL)
    {
        tmp[0] = l->n;
        tmp[1] = a * l->n + 1;
    }
    else
    {
        int *tmp2 = frac_add(l->n, l->next);
        tmp[1] = a * tmp2[1] + tmp2[0];
        tmp[0] = tmp2[1];
    }
    return tmp;
}

num * com2cont(int n, int d)    // n: numerator; d: denominator
{
    num *cont = NULL;
    addnode(&cont, n / d);
    if (n % d > 0) 
    {
        while (n % d != 1)
        {
            int tmp = d;
            d = n % d;
            n = tmp;
            addnode(&cont, n / d);
        }
        addnode(&cont, d);
    }
    return cont;
}

int * cont2com(num *l)
{
    int *tmp, *tmp2;
    tmp = (int *)malloc(2 * sizeof(int));
    if (l->next == NULL)
    { 
        tmp[0] = l->n;
        tmp[1] = 1;
    }
    else    // Note: define a stack instead of list may be better (LIFO)
    {
        tmp2 = frac_add(l->n, l->next);
        // reverse for the first step
        tmp[0] = tmp2[1];
        tmp[1] = tmp2[0];
    }
    return tmp;
}

void cont_out(num *l)
{
    cout << '[';
    cout << l->n;
    if (l->next == NULL)
        cout << ']' << endl;
    else
    {
        cout << ';';
        num *pointer = l->next;
        while (pointer != NULL)
        {
            cout << pointer->n;
            if (pointer->next != NULL)
                cout << ',';
            pointer = pointer->next;
        }
        cout << ']' << endl;
    }
}

0 条评论

目前还没有评论...

信息

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