计算在11 ^ N结果的那些数 [英] Calculate count of ones in result of 11^n

问题描述

下面的问题被要求在接受记者采访。给定一个11号 ^N （其中 N ∈ [0，1000] ），得到的计数1 S在的结果。例如n = 3，11 ³ = 1331，所以预期的结果将是2或者给定的n = 6,11 ⁶ = 1771561，预期的结果将是3。

The following problem was asked in an interview. Given a number 11ⁿ (where n ∈ [0, 1000]), get the count of 1s in the result. For example, n=3, 11³ = 1331, so the expected result would be 2. Or given n=6, 11⁶ = 1771561, the expected result would be 3.

我首先想到的是，它必须做一些与杨辉三角和< A HREF =htt​​p://en.wikipedia.org/wiki/Binomial_coefficient相对=nofollow>二项式系数（因为我们知道简单的计算 POW（11，1000）不行，至少在C）。

My first thought was that it had to do something with the pascal's triangle and binomial coefficients (because as we know simply calculating pow(11, 1000) doesn't work, at least in C).

我想通过简单地遍历列在杨辉三角应该给我的结果，但显然是行不通的。

I thought by simply iterating over the columns in the pascal's triangle should give me the result, but that clearly doesn't work.

那种所以我坚持现在。我的下一个想法是使用某种 BIGNUM库来解决这个问题，但在我看来，必须有另一种方式来解决这样的任务。

So I'm kind of stuck right now. My next thought was to use some kind of bignum library to solve the problem, but in my opinion there must be another way to solve this kind of task.

更新 我忘了提，我本来是要解决这一任务用C / Objective-C的。

Update I forgot to mention that I was supposed to solve this task with C / Objective-C.

推荐答案

像巴尔托什的建议，我会简单地进行计算基数10解决了这个由11基地10​​乘法可以用一个左移和完成加成。下面是一个C程序的ASCII字符串的作品。注意，至少显著位至上每个字符串中。

Like Bartosz suggested, I would solve this by simply performing the calculations in base 10. A multiplication by 11 in base 10 can be done with a left shift and an addition. Here's a C program that works on ASCII strings. Note that the least significant digit comes first in each string.

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

char *multiply_by_11(const char *num, int *num_ones_ptr)
{
    size_t len = strlen(num);
    char *result = (char *)malloc(len + 3);
    int carry = 0;
    int num_ones = 0;
    size_t i;

    for (i = 0; i <= len; ++i) {
        int digit = carry;

        if (i < len) {
            digit += num[i] - '0';
        }
        if (i > 0) {
            digit += num[i-1] - '0';
        }

        if (digit < 10) {
            carry = 0;
        }
        else {
            digit -= 10;
            carry = 1;
        }

        if (digit == 1) {
            ++num_ones;
        }
        result[i] = digit + '0';
    }

    if (carry) {
        result[i++] = '1';
        ++num_ones;
    }

    result[i] = '\0';

    *num_ones_ptr = num_ones;
    return result;
}

int main()
{
    char *num = (char *)malloc(2);
    int i;

    strcpy(num, "1");

    for (i = 1; i <= 1000; ++i) {
        int num_ones;

        char *product = multiply_by_11(num, &num_ones);
        printf("11 ^ %4d: %3d ones\n", i, num_ones);

        free(num);
        num = product;
    }

    free(num);
    return 0;
}

这篇关于计算在11 ^ N结果的那些数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！