algorithm算法入门


备注

算法简介

算法在计算机科学和软件工程中无处不在。选择合适的算法和数据结构可提高我们的计划成本和时间效率。

什么是算法?非正式地,算法是完成特定任务的过程。 [Skiena:2008:ADM:1410219]具体来说,算法是一个明确定义的计算过程,它将一些值(或一组值)作为输入,并产生一些值或一组值作为输出 。因此,算法是将输入转换为输出的一系列计算步骤。 Cormen et。人。没有明确指出算法不一定需要输入。 [Cormen:2001:IA:580470]

形式上,算法必须满足五个特征:[Knuth:1997:ACP:260999]

  1. 有限性 。算法必须始终在有限数量的步骤之后终止。
  2. 确定性 。必须精确定义算法的每个步骤;必须严格规定要采取的行动。正是这种质量[Cormen:2001:IA:580470]用术语“明确定义”来指代。
  3. 输入 。算法具有零个或多个输入 。这些是在算法开始之前或在运行时动态地给予算法的量。
  4. 输出 。算法具有一个或多个输出 。这些是与输入具有指定关系的数量。我们期望当一次又一次地给出相同的输入时,算法产生相同的输出。
  5. 有效性 。通常预期算法也是有效的 。它的操作必须足够基本,以便它们可以在原则上完成,并且在有限的时间内由使用铅笔和纸的人完成。

缺乏有限性但满足算法的所有其他特征的过程可以称为计算方法 。 [Knuth的:1997:ACP:260999]

一个示例算法问题

算法问题是通过在其中一个实例上运行后描述它必须处理的完整实例集及其输出来指定的。问题和问题实例之间的这种区别是至关重要的。称为排序的算法问题定义如下:[Skiena:2008:ADM:1410219]

  • 问题:排序
  • 输入: n个键的序列, a_1, a_2, ..., a_n
  • 输出:输入序列的重新排序,使得a'_1 <= a'_2 <= ... <= a'_{n-1} <= a'_n

排序的实例可以是字符串数组,例如{ Haskell, Emacs } 或一系列数字,例如{ 154, 245, 1337 }

Swift中简单Fizz Buzz算法入门

对于那些刚接触Swift编程的人以及来自不同编程基础的人,例如Python或Java,本文应该非常有用。在这篇文章中,我们将讨论一个实现swift算法的简单解决方案。

Fizz Buzz

您可能已经将Fizz Buzz视为Fizz Buzz,FizzBu​​zz或Fizz-Buzz;他们都指的是同一件事。这个“事物”是今天讨论的主要话题。首先,什么是FizzBu​​zz?

这是求职面试中常见的问题。

想象一下从1到10的一系列数字。

1 2 3 4 5 6 7 8 9 10
 

Fizz和Buzz分别指的是3和5的倍数。换句话说,如果一个数字可被3整除,则用fizz代替;如果一个数字可被5整除,则用buzz代替。如果一个数字同时是3和5的倍数,则该数字将替换为“fizz buzz”。从本质上讲,它模仿了着名的儿童游戏“fizz buzz”。

要解决此问题,请打开Xcode以创建一个新的游乐场并初始化如下所示的数组:

// for example 
let number  = [1,2,3,4,5]
// here 3 is fizz and 5 is buzz
 

为了找到所有的嘶嘶声和嗡嗡声,我们必须遍历数组并检查哪些数字是嘶嘶声,哪些是嗡嗡声。为此,创建一个for循环来迭代我们初始化的数组:

for num in number {
  // Body and calculation goes here
}
 

在此之后,我们可以简单地使用“if else”条件和模块运算符在swift ie - %中找到fizz和buzz

for num in number {
  if num % 3 == 0 {
    print("\(num) fizz")
  } else {
    print(num)
  }
}
 

大!您可以转到Xcode playground中的调试控制台查看输出。您会发现“fizzes”已经在您的数组中进行了整理。

对于Buzz部分,我们将使用相同的技术。在滚动浏览文章之前,我们先尝试一下 - 完成此操作后,您可以根据本文检查结果。

for num in number {
  if num % 3 == 0 {
    print("\(num) fizz")
  } else if num % 5 == 0 {
    print("\(num) buzz")
  } else {
    print(num)
  }
}
 

检查输出!

这是相当直接的 - 你将数字除以3,fizz并将数字除以5,嗡嗡声。现在,增加数组中的数字

let number = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
 

我们将数字范围从1-10增加到1-15,以展示“嘶嘶声”的概念。由于15是3和5的倍数,因此该数字应替换为“fizz buzz”。试试自己并检查答案!

这是解决方案:

for num in number {
  if num % 3 == 0 && num % 5 == 0 {
    print("\(num) fizz buzz")
  } else if num % 3 == 0 {
    print("\(num) fizz")
  } else if num % 5 == 0 {
    print("\(num) buzz")
  } else {
    print(num)
  }
}
 

等等......但它还没结束!该算法的整个目的是正确定制运行时。想象一下,如果范围从1-15增加到1-100。编译器将检查每个数字以确定它是否可被3或5整除。然后它将再次遍历数字以检查数字是否可被3和5整除。代码基本上必须遍历数组中的每个数字两次 - 它必须首先运行数字3然后再运行5.为了加快这个过程,我们可以简单地告诉我们的代码将数字直接除以15。

这是最终的代码:

for num in number {
  if num % 15 == 0 {
    print("\(num) fizz buzz")
  } else if num % 3 == 0 {
    print("\(num) fizz")
  } else if num % 5 == 0 {
    print("\(num) buzz")
  } else {
    print(num)
  }
}
 

简单到这一点,您可以使用您选择的任何语言并开始使用

享受编码