标签: computer-science

我一直在研究最近的计算机科学作业,包括递归和大O符号.我相信我很了解这一点(当然不是很完美!)但是有一个问题特别是给我最多的问题.奇怪的是,通过观察,它看起来是家庭作业中最简单的一个.

使用big-Oh表示法提供最佳增长率,以解决以下重现问题？

T(1)= 2

对于n> 1,T(n)= 2T(n-1)+ 1

选择是:

• O(n log n)
• 为O(n ^ 2)
• O(2 ^ n)的
• 为O(n ^ n)的

我知道大O作为一个上限,用于描述该程序或过程将采取的大部分计算或最高运行时间.我觉得这个特殊的递归应该是O(n),因为最多只有n的每个值都会发生一次递归.由于n不可用,它要么比那更好,O(nlogn),或者更糟糕的是,作为其他三个选项.

所以,我的问题是:为什么不是这个O(n)？

所以我希望能够在C#中解析和评估"骰子表达式".骰子表达式定义如下:

<expr> :=   <expr> + <expr>
            | <expr> - <expr>
            | [<number>]d(<number>|%)
            | <number>
<number> := positive integer

所以例如d6+20-2d3是允许的,并且应该评估为

rand.Next(1, 7) + 20 - (rand.Next(1, 4) + rand.Next(1, 4))

也d%应该相当于d100.

我知道我可以解决一些解决方案,但我也知道这似乎是一个非常典型的计算机科学类型的问题,所以必须有一些我应该研究的超优雅解决方案.

我希望我的解析结果具有以下功能:

• 我应该能够输出表达式的规范化形式; 我首先考虑骰子,按骰子大小排序,并始终使用前缀.所以例如上面的样本会变成1d6-2d3+20.任何实例d%也会变成d100标准化形式.
• 我应该能够随意评估表达式,每次滚动不同的随机数.
• 我应该能够用最大化的所有骰子卷来评估表达式,因此例如上面的样本将给出(确定性地)1*6+20+2*3 = 32.

我知道这正是Haskell的类型,可能还有其他功能类型的语言,但是如果可能的话,我想留在C#中.

我最初的想法倾向于递归,列表,也许还有一些LINQ,但是,如果我尝试没有知道事物的人的一些指示,我肯定它最终会成为一个不优雅的混乱.

另一种可能有效的策略是一些基于正则表达式的初始字符串替换,将骰子表达式转换为rand.Next调用,然后进行即时评估或编译......这实际上有用吗？我怎么能避免rand每次都创建一个新对象？

我们有两个列表,让我们说学生和他们的分数.我想比较这两个列表并找到新列表和旧列表之间的差异,然后找到插入或更新到新列表中的任何更改的最不具侵入性的方法.解决这个问题的最佳算法是什么？希望专注于对新列表和性能的最小量更改.

示例代码:

List<ListItem> existingList = new List<ListItem>();
List<ListItem> newList = new List<ListItem>();

public TopLists()
{
  InitTwoLists();
}

private void InitTwoLists()
{
  existingList.Add(new ListItem { Name = "Shane", Score = 100 });
  existingList.Add(new ListItem { Name = "Mark", Score = 95 });
  existingList.Add(new ListItem { Name = "Shane", Score = 94 });
  existingList.Add(new ListItem { Name = "Steve", Score = 90 });
  existingList.Add(new ListItem { Name = "Brian", Score = 85 });
  existingList.Add(new ListItem { Name = "Craig", Score = 85 …

你如何在长长的角色中找到正确的单词？

输入:

"The revised report onthesyntactictheoriesofsequentialcontrolandstate"

谷歌的输出:

"The revised report on syntactic theories sequential controlandstate"

(考虑到他们产生输出的时间足够接近)

您认为Google如何做到这一点？你会如何提高准确度？

只是想知道是否有人可以解释为什么"不稳定的排序"被认为是坏的？基本上我没有看到任何真正重要的情况.有人可以提供吗？

在类图中,我通常会看到像ClassA这样的东西扩展了ClassB,其中箭头指向ClassA.例如,这里,http://bit.ly/GFakDu.这一直困扰着我.为什么箭头不指向ClassB？

在Quora上阅读社区维基之后,我决定开始尝试使用GitHub.我想,"实验比用计算机科学入门作业更好？" 然而,这种做法打开了我对网络的解决方案,我担心其他学生可能会剽窃它.我已经在StackOverflow上阅读了有关版本控制和家庭作业的其他问题.

因此,当我考虑这种做法时,会想到一些问题:

1. 将家庭作业代码放在GitHub上是否可以复制？
2. 剽窃的人是否熟悉GitHub？
3. 我应该担心吗？
4. 抄袭检测软件会扫描GitHub

给定: set (),with .A = {a0, a1, ..., aN-1}1 ≤ N ≤ 1002 ≤ ai ≤ 500

问:找到所有A大小至少为2的子集的所有最小公倍数(LCM)的总和.

一组的LCM 被定义为最小整数,使得对于所有.B = {b0, b1, ..., bk-1}Bminbi | Bmin0 ≤ i < k

例:

让N = 3与A = {2, 6, 7},则:

LCM({2, 6})      =    6
LCM({2, 7})      =   14
LCM({6, 7})      = …

我最近在lambda演算中编写了很多程序,我希望我可以实时运行其中一些程序.然而,尽管趋势功能范例基于lambda演算和B减少规则,但我找不到一个不是玩具的单一评估者,而不是效率.功能语言应该很快,但我知道的那些实际上并不提供对普通表单的访问(参见Haskell的惰性求值程序,Scheme的闭包等),因此不能用作LC求值程序.

这让我想知道:只是不可能有效地评估lambda演算术语,它只是一个历史事故/缺乏兴趣,没有人决定为它创建一个快速评估者,或者我只是缺少一些东西？

我得到一个java问题,给出一个字符串,返回由前两个字符组成的字符串,所以String"Hello"产生"He".

如果字符串短于长度2,则返回任何内容,因此"X"产生"X",空字符串""产生空字符串"".

请注意,str.length()返回字符串的长度.

public String firstTwo(String str) {          

 if(str.length()<2){
     return str;
 }
 else{
     return str.substring(0,2);
 }
}

我想知道有没有其他办法可以解决这个问题？