free函数怎么正确使用，求大神解答。

free函数如何正确使用，求大神解答。。
这是我做的ACM的一道题，有个地方实在想不明白错在哪。。求大神帮看看
先上题：

It was said that when testing the first computer designed by von Neumann, people gave the following problem to both the legendary professor and the new computer: If the 4th digit of 2^n is 7, what is the smallest n? The machine and von Neumann began computing at the same moment, and von Neumann gave the answer first.

Now you are challenged with a similar but more complicated problem: If the K-th digit of M^n is 7, what is the smallest n?

Input

Each case is given in a line with 2 numbers: K and M (< 1,000).

Output

For each test case, please output in a line the smallest n.

You can assume:

The answer always exist.
The answer is no more than 100.
Sample Input

3 2
4 2
4 3
Sample Output

15
21
11

题目很简单，但用到大数乘法，以下是我的代码

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

void reverse(char *s)
{
    int len = strlen(s);
    int i, j;
    char c;
    for (i = 0, j = len - 1; i < j; i++, j--)
    {
        c = *(s + i);
        *(s + i) = *(s + j);
        *(s + j) = c;
    }
}

char *appendTailZero(char *s, int zeros)
{
    int i, len = strlen(s);
    char *r = malloc(len + zeros + 1);
    for (i = 0; i < len; i++)
        *(r + i) = *(s + i);
    for (i = len; i < len + zeros; i++)
        *(r + i) = '0';
    *(r + len + zeros) = '\0';
    return r;
}

char *add(char *s1, char *s2)
{
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    int len = l1 > l2 ? l1 : l2;
    char *r = malloc(len + 2);
    int i, prev = 0, a, b, sum;
    for (i = 0; i < len; i++)
    {
        a = l1 - 1 - i >= 0 ? *(s1 + l1 - 1 - i) - '0' : 0;
        b = l2 - 1 - i >= 0 ? *(s2 + l2 - 1 - i) - '0' : 0;
        sum = a + b + prev;
        *(r + i) = sum > 9 ? sum - 10 + '0' : sum + '0';
        prev = sum > 9 ? 1 : 0;
    }
    if (prev)
    {
        *(r + len) = '1';
        *(r + len + 1) = '\0';
    }
    else
        *(r + len) = '\0';
    reverse(r);
    return r;
}

char *multiplyHelper(char *s1, int digit)
{
    int i, res, prev = 0, len = strlen(s1);
    char *r = malloc(len + 2);
    if (!digit)
    {
        *r = '0';
        *(r + 1) = '\0';
        return r;
    }

    for (i = 0; i < len; i++)
    {
        res = (*(s1 + len - 1 - i) - '0') * digit + prev; 
 
        *(r + i) = res % 10 + '0';
        prev = res / 10;
    }
    if (prev)
    {
        *(r + len) = prev + '0';
        *(r + len + 1) = '\0';
    }
    else
        *(r + len) = '\0';
    reverse(r);
    return r;
}

char *multiply(char *s1, char *s2)
{
    if (strlen(s1) < strlen(s2))
    {
        char *temp;
        temp = s1;
        s1 = s2;
        s2 = temp;
    }
    int l2 = strlen(s2);
    int i;
    char *t, *zt;
    char *sum = malloc(2);
    char *tp;
    sum = "0";
    for (i = 0; i < l2; i++)
    {
        tp = sum;
        t = multiplyHelper(s1, *(s2 + l2 - 1 - i) - '0');
        zt = appendTailZero(t, i);
        sum = add(tp, zt);
        free(t);
        free(zt);
        free(tp);//加入这行代码提交就报Runtime Error, 不加就Accepted,但是内存占用很大
    }
    return sum;
}

int main()
{
    int k;
    char m[5];
    while (scanf("%d %s", &k, m) != EOF)
    {
        char *r = m;
        int count = 1;
        while (strlen(r) < k)
        {
            r = multiply(r, m);
            count++;
        }
        r = r + strlen(r) - k;
        while (*r != '7')
        {
            r = multiply(r, m);
            r = r + strlen(r) - k;
            count++;
        }
        printf("%d\n", count);
    }
    return 0;
}

疑问就出在我注释的那行代码上，由于乘法中间用到了加法，因此每次都会产生加和的临时变量，我想把这些内存free掉，但是一加上这行代码提交就报Runtime Error, 在本地运行没有问题，去掉后提交可以过，但是内存占用很大。想问问这个地方free使用哪里出错了？我free的变量都是前一次的sum结果。。还有最后main函数里面每次做乘法的临时变量内存也可以free，但是加了类似代码也报错。。自己实在想不明白，求大神们帮看看啊，新手分不多见谅
[解决办法]
第一次进循环的时候，sum="0",tp=sum，这时候tp指向了常量字符串“0”，这种怎么能free呢？
[解决办法]
讨厌的CSDN不许连续回复超过3次！

回到这题，如果没有聪明的方法(估计有), 就用你的暴力法，那你的乘法实现还是太低效率了，即使写对了也10有8、9会timeout. 其实根本不需要那么多次动态分配内存，

已知M<1000, n<100, 所以M^n不大于10^300， 你直接在堆上开一个300的数组，就对它操作，这样一次malloc和free都不用，会大大提高你的程序的效率。

还可以再提高，你用一个字符来表示一个十进制的数位，这当然可以得到正确的结果，但效率还可以提高。
可以相信目标机器不会低于32位处理器，更准确的说法应该是目标机器上的c编译器的sizeof(int)不会低于4. 你完全可以用size_t或者int数组(instead of char[]), 在int间用10^9进位，每个int降级到10^9进位，即如果一个整数存的是10^9-1， 对它increment后，它会归0，而高位整数进一......希望你听懂了我的意思。这样的好处是计算更紧凑而保留了快速检查第k位是否为7的能力......


如果你能看懂我上面的意思，建议你用那个思路再实现一遍，甚至对比实现一遍，比较两者的效率，假定可以通过ACM的机器检测。

哦，你没必要定义乘法(*)，定义自乘(*=)就好了。形如:

void multiply_by(int self[], int num);

其中的self是一个足够装下10^300次方，成员间10^9进位的整型数组（啰嗦一下，每个成员装10^9, 10^300需要34个这样的int, 可以想一下你原来用成员用char，成员间10进位的方案要用300个元素, 哪一个会更快？)

你先试试，搞不定再问吧。
[解决办法]
free函数只能释放通过malloc、realloc、calloc函数开辟的内存，你的代码里sum开始是malloc的，但是你紧接着就把sum指向了“0”（这里实际上已经造成了内存泄漏），后面tp又指向了sum指向的地址即“0”，这样的地址不是通过上述三个函数分配的，所以会报错。

查看更多 下一篇