0

在今年的 Google Code Jam 中，我无法解决排位赛的一个问题。这个（底部的完整代码）是我想出的解决公平和正方形问题的方法。并且，它被判定为不正确，两次。

而且，它令人痛苦地士气低落。我打算在下一次 Google Code Jam 中改变这种情况。我知道一个人必须练习（很多！）才能成为更好的程序员，成为专家需要数年时间。我相信我已经准备好付出那么多努力。但是，一个人很容易被要掌握的东西列表的大小所淹没。所以，我的问题是，是否可以设计一条学习路径，以便人们能够识别和掌握在 Google Code Jam 或类似项目中表现更好所需的技能在线比赛？如果是，那会是什么？

这条路径应该允许一个人先掌握更简单的技术，然后再转向更难的技术，好像难度级别逐渐增加一样。

这是我对公平和正方形问题的（错误）解决方案

#include<stdio.h>
#include<math.h> 
int sqrRoot(double numberToCheck);
int isPalindrome(int numToCheck);


int main(void)
{
int i=0,j=0,cases=1,steps=0,low=0,high=0,isSquare=0,count=0,bit=0;
scanf("%d", &steps);

while (cases<=steps)
{
    scanf(" %d %d", &low, &high );
    for (j=low;j<=high;j++)
    {
        isSquare = sqrRoot(j);
        if (isSquare == 1)
        {
            bit = isPalindrome(j);
            if (bit==1)
            {
                count ++;
                //printf("\n wowowo# %d", j);
            }
        }
    }

    printf("Case #%d: %d \n", cases,count);
    count = 0;
    bit = 0;
    cases++;
}

return 0;
}

int sqrRoot(double numberToCheck)
{

double result = sqrt(numberToCheck);
int y=0;
y = result;
 if (result == y)
 {

    return 1;
 }

 else
 {
    return 0;
 }
}


int isPalindrome(int numToCheck)
{
  int n=0,rev=0;
  double dig=0.0;
  n = numToCheck;

  while(numToCheck>0)
 {
   dig = numToCheck % 10;
       rev = rev * 10 + dig;
       numToCheck = numToCheck / 10;
 }

  if (n==rev)
 {
   return 1;
 }

  return 0;
}
4

3 回答 3

3

看来，鉴于您对要学习的技能清单如此长且令人生畏的描述，最好的方法是仅间接地为这场比赛做准备，并直接尽可能多地专注于学习计算机科学。作为一个中间人（并且不断努力学习更多），我可以说我学到最多的时期是我不寻求获得地位（例如通过获奖）但诚实地试图效仿工艺大师。例如，在计算机科学方面，阅读像 Peter Norvig 这样的人（通过他的书籍和 MOOC 课程）编写的书籍并尝试复制他们的代码，这让我的技能来之不易但显着提高。我想说的是，最重要的是，

于 2013-04-14T05:24:26.413 回答
1

You need to master Algorithms and Data Structures. There is one book that you can read online for free that I highly recommend: Algorithms by Dasguspta.

Coursera.org has some courses on this too. Sedgewick's is really good and his book is a nice addition to any bookshelf.

You can also practice with ACM problems or TopCoder, which also provides some good tutorials

于 2013-04-14T11:48:20.793 回答
1

我不是算法竞赛的专家，但他们要求你做一项与现实世界算法问题解决非常不同的工作。首先，它们通常需要一个精确的解决方案，而在现实生活中，近似值通常可能是一个非常好的选择。它简化了验证：只有一个输出是可能的。此外，如果您可以通过近似来解决许多难题，那么它们就会变得微不足道。第二个区别是组织者必须确保为一个问题获得的分数与问题的难度有关。这个问题不能有一个微不足道的解决方案，并且必须需要一些工作才能解决。这意味着大多数问题都是众所周知的问题的变体，竞争者必须找到如何使通常的算法适应这个问题。通过这种方式，人们可以判断他们适应这些算法的速度和效果。

对您而言，这意味着您必须了解常用的优化算法。幸运的是，有关于它们的书籍。不幸的是，我不认识他们。（我主要在大学学习）如果你想最大化你的机会，你最好使用这些通用算法：

  • 寻路（Dept-first、Breath-first、Best-first、Dijkstra、A*）
  • 动态规划
  • 分支与绑定
  • 潜水与征服
  • 约束编程
  • 图算法
  • 也许Flow network，但不确定你是否需要它

这些主题重叠，通常不容易找到哪一个有用。现在，这只是理论。就像我说的那样，困难在于使它们适应您遇到的问题。为此，你只能训练很多。还需要培训，因为它将帮助您了解如何快速有效地实施它们。编写这些算法的方法有很多种，有了经验，您就会了解它们（谷歌会提供帮助）并知道如何选择它们。当然，你不能启动 google code jam，看着一些问题然后说......“嗯......它记得我在书中读到的一些问题”你会浪费太多时间尝试第一次实现它时间。这与现实世界的算法也有很大的不同。

不管怎样，还有很多其他的比赛。如果您满足要求，您应该尝试它们。它通常很有趣和有趣。

您的解决方案是我们能找到的关于公平与平方问题的最简单的解决方案。当然，这还不够：您总是必须找到比第一个解决方案更好的解决方案。我相信你的 isSquare 函数是错误的。浮点运算会增加小的不精确性，这可能会改变非常简单的测试，例如您编写的测试。

您的算法的成本来自您测试的数字数量。这些数字可能很大（顺便说一句，您的代码不适用于这些巨大的数字，因为它们不能存储在 C 的通常的 32 位整数中）并且迭代它们可能需要很长时间。为了改善这一点，您可以直接遍历平方根。如果您r从sqrt(A)to迭代sqrt(B)，那么您确定 是from tor*r的所有正方形。因此，您不必测试它们的平方根是否为整数，并且要测试的数字要少得多。AB

这个想法很经典：减小要迭代的空间大小。您可以通过仅迭代回文根来进一步改进算法。公平和平方根也有一些数学性质，但我懒得证明它，所以我没有寻找其他改进。这是关于你的问题的最后一句话：你可能需要基本的数学知识来解决一些问题。通常，算法技能也是证明您使用的算法的能力。

于 2013-04-14T12:35:42.037 回答