三色三角形

问题描述 投票：0回答：4

我正在尝试为这个问题编写代码：

（来源：https://www.codewars.com/kata/insane-coloured-triangles/train/c）

彩色三角形由一排颜色组成，每一种颜色都是 红色、绿色或蓝色。连续的行，每行少一种颜色 比上一个，是通过考虑两种接触颜色产生的 在前一行。如果这些颜色相同，则颜色相同 在新行中使用。如果它们不同，则缺少的颜色是 在新行中使用。这一直持续到最后一行，只有 生成单一颜色。

例如，不同的可能性是：

Colour here:            G G        B G        R G        B R 
Becomes colour here:     G          R          B          G 

With a bigger example:
   R R G B R G B B  
    R B R G B R B
     G G B R G G
      G R G B G
       B B R R
        B G R
         R B
          G

您将获得三角形的第一行作为字符串，您的工作是返回将作为字符串出现在底行中的最终颜色。在上面的例子中，你会得到

'RRGBRGBB'
，你应该返回
'G'
。

约束条件：

1 <= length(row) <= 10 ** 5

输入的字符串将只包含大写字母'

B', 'G' or 'R'
.

具体的测试用例数量如下：

100 tests of 100 <= length(row) <= 1000 
100 tests of 1000 <= length(row) <= 10000 
100 tests of 10000 <= length(row) <= 100000

例子：

triangle('B') == 'B'
triangle('GB') == 'R'
triangle('RRR') == 'R'
triangle('RGBG') == 'B'
triangle('RBRGBRB') == 'G'
triangle('RBRGBRBGGRRRBGBBBGG') == 'G'

所以我制作了这段代码，它适用于所有样本口味，但是当它出现在

length of row > 25
时，由于我的阶乘函数，它失败了，并且在某些情况下长度达到
100,000
，所以任何解决这个问题的建议至少任何可以解决问题的数学公式或小提示。

顺便说一句，我在找到解决该站点问题的数学方法后编写了这段代码：

https://math.stackexchange.com/questions/2257158/three-color-triangle-challenge

long long factorial(long long num)     
{
    long long fact = num;

    if (fact == 0)
        fact = 1;

    while (num > 1)
    {
        num--;
        fact *= num;
    }
    return (fact);
}

long long combination(long long n, long long k, long long fact_n)
{
    long long fact_k = factorial(k);
    long long comb = ( fact_n / (fact_k * factorial(n - k)) );
    return (comb);
}

char triangle(const char *row)
{
    long long len = strlen(row);
    long long n = len - 1;
    long long k = 0;
    int sign = pow(-1,n);
    long long sum = 0;
    char *result = "RGB";
    int a;
    long long fact_n = factorial(n);

    while (k < len)                 //This while calculate Segma (∑). 
    {
        if (row[k] == 'R')
            a = 0;
        else if (row[k] == 'G')
            a = 1;
        else if (row[k] == 'B')
            a = 2;

        if (a != 0)
            sum = sum + (combination(n,k,fact_n) * a); 
        k++;
    }

    sum = sign * (sum % 3);

    if (sum == -1 || sum == -2)
        sum += 3;

  return (result[sum]);
}
c math probability factorial
4个回答
11
投票

我假设您提供的链接中的公式是正确的：

为了避免整数溢出，我们需要应用这些模运算规则：

(a * b) mod c = ((a mod c) * (b mod c)) mod c

(a ± b) mod c = ((a mod c) ± (b mod c)) mod c

将它们应用于公式：

但是我们如何计算

...没有直接计算系数本身（这会导致溢出）？

因为 3 是素数，这可以用 卢卡斯定理：

... 其中 

n_i, m_i
是 
i
在 
base-3
. 中的第 n, m

位

通过整数除法很容易转换为 base-3：

// convert a number to base 3
// and returns the number of digits
unsigned conv_base_3(unsigned n, unsigned max, unsigned* out)
{
    unsigned i = 0;
    while (i < max && n > 0)
    {
        out[i] = n % 3;
        n /= 3;
        i++;
    }
    return i;
}

请注意，由于 

n_i, m_i
始终在 
[0, 2]
范围内（因为它们是 base-3 数字），所以 
C(n_i, m_i)
非常容易计算：

// calculate the binomial coefficient for n < 3
unsigned binom_max_2(unsigned n, unsigned k)
{
    if (n < k)
        return 0;
    switch (n)
    {
        case 0:
        case 1:
            return 1;
        case 2:
            return 1 + (k == 1);

        // shouldn't happen
        default:
            return 0;
    }
}

现在定理本身：

// Lucas's theorem for p = 3
unsigned lucas_3(unsigned len_n, const unsigned * dig_n,
                 unsigned len_k, const unsigned * dig_k)
{
    // use modulo product rule:
    // prod[i] % 3 = ((prod[i - 1] % 3) * value[i])      
    unsigned prod = 1;
    for (unsigned i = 0; i < len_n; i++) {
        unsigned n_i = dig_n[i];
        unsigned k_i = (i < len_k) ? dig_k[i] : 0;
        prod = (prod * binom_max_2(n_i, k_i)) % 3;
    }
    return prod % 3;
}

字符转换：

// convert from 012 to RGB
char int_2_char(int i)
{
    switch (i) {
        case 0: return 'R';
        case 1: return 'G';
        case 2: return 'B';

        // shouldn't happen
        default:
            return '\0';
    }
}

// convert from RGB to 012
unsigned char_2_int(char c)
{
    switch (c) {
        case 'R': return 0;
        case 'G': return 1;
        case 'B': return 2;

        // shouldn't happen
        default:
            return 3;
    }
}

最后是三角算法：

// the problem constraints state that n <= 10 ** 5
// max number of base-3 digits
#define MAX_N_LOG_3 11

// main algorithm function
char triangle(const char * input)
{
    unsigned sum = 0;
    const int n = strlen(input);

    // calculate digits of n - 1
    unsigned dig_n[MAX_N_LOG_3];
    unsigned len_n = conv_base_3(n - 1, MAX_N_LOG_3, dig_n);

    for (unsigned km1 = 0; km1 < n; km1++)
    {
        // calculate digits of k - 1
        unsigned dig_k[MAX_N_LOG_3];
        unsigned len_k = conv_base_3(km1, MAX_N_LOG_3, dig_k);

        // calculate C(n - 1, k - 1) mod 3
        unsigned Cnk_mod3 = lucas_3(len_n, dig_n, len_k, dig_k);

        // add using the modulo rule
        sum = (sum + Cnk_mod3 * char_2_int(input[km1])) % 3;
    }

    // value of (-1) ** (n - 1)
    // no need for pow; just need to know if n is odd or even
    int sign = (n % 2) * 2 - 1;

    // for negative numbers, must resolve the difference
    // between C's % operator and mathematical mod
    int sum_mod3 = (3 + (sign * (int)(sum % 3))) % 3;
    return int_2_char(sum_mod3);
}

以上代码通过了所有测试。请注意，它是为了清晰而不是性能而编写的。

那么为什么这段代码能够在分配的时间内通过所有测试，而简单的基于表的方法却不能？因为它的时间复杂度：

  • 基于表格的方法处理三角形的所有级别，即

    O(n^2)
    （参见Triangle Numbers）。

  • 当然，使用Lucas的算法，只需要处理top level；然而算法本身是

    O(log n)
    ，因为它循环遍历
    n
    的每个数字（不管基数）。整体复杂度为
    O(n log n)
    ，仍然代表着显着的提升

1
投票

const triangle = row => {
  let reduced = row.length > 1 ? '' : row;
  for (let i = 0; i < row.length - 1; i += 1) {
    reduced += row[i] == row[i + 1] ? row[i] : 'RGB'.replace(row[i], '').replace(row[i + 1], '');
  }
  return reduced.length > 1 ? triangle(reduced) : reduced;
}
triangle('B') == 'B'
triangle('GB') == 'R'
triangle('RRR') == 'R'
triangle('RGBG') == 'B'
triangle('RBRGBRB') == 'G'
triangle('RBRGBRBGGRRRBGBBBGG') == 'G'

const triangle = row => {
  let reduced = row.length > 1 ? '' : row;
  for (let i = 0; i < row.length - 1; i += 1) {
    reduced += row[i] == row[i+1] ? row[i] : 'RGB'.replace(row[i], '').replace(row[i+1], '');
  }
  return reduced.length > 1 ? triangle(reduced) : reduced;
}

0
投票
def triangle(x):
l =len(x)
v=l
R=""

for j in range(v-1):
    for i in range(l-1):
        la=[x[i],x[i+1]]
        if x[i]==x[i+1]:
            R+=x[i]
        else:
            if "R" not in la:
                R+= "R"
            elif "G" not in la:
                R+= "G"
            else:
                R+= "B"
    x=R    
    R=""
    l=len(x)
return (x)
-1
投票

递归在这里没什么用，因为你永远不必返回到以前的状态。迭代是一个更好的解决方案，可以相当简单地完成。

对初始字符串的更改也可以就地进行，因为一旦使用和更改它就永远不需要返回到原始值。

方法如下。只要字符串大于一个字符，就处理原始字符串中的每组两个字符（重叠）。

对于那对，根据您的规则更改第一个字符。完成所有对后，从字符串中删除最后一个字符，导致字符串少一个字符。

下面是一些示例代码，展示了这一点，具有不必要但有用的检查和输出功能：

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

// Helper function to output nicely spaced string.

static void output(int gap, char *str) {
    // Spaces at line start.

    while (gap-- > 0)
        putchar(' ');

    // Actual string with spaces between letters, end line following.

    while (*str != '\0') {
        putchar(' ');
        putchar(*str++);
    }
    putchar('\n');
}

// The meat of the solution.

int main(int argc, char *argv[]) {
    // Check parameter count and content.

    if (argc != 2) {
        fprintf(stderr, "*** Needs one argument\n");
        return 1;
    }

    size_t strSz = strlen(argv[1]);
    if (strSz == 0) {
        fprintf(stderr, "*** Argument too short\n");
        return 1;
    }
    printf("String size is %ld\n", strSz);
    int debug = (strSz <= 20);

    for (char *str = argv[1]; *str != '\0'; str++) {
        if (*str == 'R' || *str == 'G' || *str == 'B')
            continue;
        fprintf(stderr, "*** Bad character '%c' found\n", *str);
        return 1;
    }

    // Continue until you have a short enough string.

    int spaces = 0;
    while (strSz > 1) {
        // Output current string, update spaces for next.

        char *str = argv[1];
        if (debug)
            output(spaces++, str);

        // Process each overlapping pair in string.

        while (*str != '\0') {
            if      (*str == 'G' && *(str + 1) == 'R') *str = 'B';
            else if (*str == 'R' && *(str + 1) == 'G') *str = 'B';
            else if (*str == 'B' && *(str + 1) == 'G') *str = 'R';
            else if (*str == 'G' && *(str + 1) == 'B') *str = 'R';
            else if (*str == 'B' && *(str + 1) == 'R') *str = 'G';
            else if (*str == 'R' && *(str + 1) == 'B') *str = 'G';

            str++;
        }
        *(str - 1) = '\0';
        strSz--;
    }

    // Output final one-character string.

    if (debug)
        output(spaces, argv[1]);
    else
        puts(argv[1]);

    return 0;
}

使用参数 

RRGBRGBB
运行时该代码的输出如预期的那样：

String size is 8
 R R G B R G B B
  R B R G B R B
   G G B R G G
    G R G B G
     B B R R
      B G R
       R B
        G

它也适用于最多限制（100,000 个字符）的字符串，但请记住它是一个 O(n2) 解决方案，因此随着大小变大，速度会变慢。对随机 100,000 个字符的字符串进行的测试在不到 15 秒的时间内完成，因此，如果需要比这更快，则此解决方案不合适。为了完整起见，这是我系统上各种输入大小的运行时表（禁用调试输出）：

Input size   Run time
----------   --------
         1    0.001 s
        10    0.002 s
       100    0.002 s
      1000    0.005 s
     10000    0.141 s
    100000   14.331 s

它超过了 20,000 到 30,000 个字符之间的一秒阈值。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.