当前位置:   article > 正文

3.数组算法、动态规划_数组动态规划

数组动态规划

数组算法

Array是一个容器,可以容纳固定数量的项目,这些项目应该是相同的类型。大多数数据结构都使用数组来实现其算法。以下是理解Array概念的重要术语。

  • 元素 - 存储在数组中的每个项称为元素。
  • 索引 - 数组中元素的每个位置都有一个数字索引,用于标识元素。

1.数组表示

可以使用不同语言以各种方式声明数组。为了说明,我们采取C数组声明。

在这里插入图片描述

可以使用不同语言以各种方式声明数组。为了说明,我们采取C数组声明。

)

根据以上说明,以下是要考虑的重点。

  • 索引从0开始。
  • 数组长度为10,这意味着它可以存储10个元素。
  • 可以通过索引访问每个元素。例如,我们可以将索引6处的元素提取为9。

2.基本操作

以下是数组支持的基本操作。

  • 遍历 - 逐个打印所有数组元素。
  • 插入 - 在给定索引处添加元素。
  • 删除 - 删除给定索引处的元素。
  • 搜索 - 使用给定索引或值搜索元素。
  • 更新 - 更新给定索引处的元素。

在C中,当使用size初始化数组时,它会按以下顺序为其元素分配默认值。

数据类型默认值
布尔
烧焦0
INT0
浮动0.0
0.0F
空虚
wchar_t的0

3.插入操作

插入操作是将一个或多个数据元素插入到数组中。根据需求,可以在开头,结尾或任何给定的数组索引处添加新元素。

在这里,我们看到插入操作的实际实现,我们在数组的末尾添加数据 -

算法

ArrayMAX 元素的线性无序数组。

实例1

结果

LA 是一个线性阵列(无序的)与 Ñ 元件和 ķ 是一个正整数,使得 ķ <= N。以下是将ITEM插入洛杉矶第 K 个位置的算法-

1. Start
2. Set J = N
3. Set N = N+1
4. Repeat steps 5 and 6 while J >= K
5. Set LA[J+1] = LA[J]
6. Set J = J-1
7. Set LA[K] = ITEM
8. Stop
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

实例2

以下是上述算法的实现 -

#include <stdio.h>

main() {
   int LA[] = {1,3,5,7,8};
   int item = 10, k = 3, n = 5;
   int i = 0, j = n;

   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   n = n + 1;

   while( j >= k) {
      LA[j+1] = LA[j];
      j = j - 1;
   }

   LA[k] = item;

   printf("The array elements after insertion :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

当我们编译并执行上述程序时,它会产生以下结果 -

输出

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

3.删除操作

删除是指从数组中删除现有元素并重新组织数组的所有元素。

算法

考虑 LA 是一个线性阵列 Ñ 元件和 ķ 是一个正整数,使得 ķ <= N。以下是删除在LA的第 K 个位置可用的元素的算法。

1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

实例1

以下是上述算法的实现

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5;
   int i, j;

   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   j = k;

   while( j < n) {
      LA[j-1] = LA[j];
      j = j + 1;
   }

   n = n -1;

   printf("The array elements after deletion :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

当我们编译并执行上述程序时,它会产生以下结果 -

输出

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

4.搜索操作

您可以根据数组元素的值或索引搜索数组元素。

算法

考虑 LA 是一个线性阵列 Ñ 元件和 ķ 是一个正整数,使得 ķ <= N。以下是使用顺序搜索查找具有ITEM值的元素的算法。

1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

实例2

以下是上述算法的实现

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int item = 5, n = 5;
   int i = 0, j = 0;

   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   while( j < n){
      if( LA[j] == item ) {
         break;
      }

      j = j + 1;
   }

   printf("Found element %d at position %d\n", item, j+1);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

当我们编译并执行上述程序时,它会产生以下结果 -

输出

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

5.更新操作

更新操作是指在给定索引处更新阵列中的现有元素。

算法

考虑 LA 是一个线性阵列 Ñ 元件和 ķ 是一个正整数,使得 ķ <= N。以下是更新在LA的第 K 个位置可用的元素的算法。

1. Start
2. Set LA[K-1] = ITEM
3. Stop
  • 1
  • 2
  • 3

实3例

以下是上述算法的实现 -

#include <stdio.h>

void main() {
   int LA[] = {1,3,5,7,8};
   int k = 3, n = 5, item = 10;
   int i, j;

   printf("The original array elements are :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }

   LA[k-1] = item;

   printf("The array elements after updation :\n");

   for(i = 0; i<n; i++) {
      printf("LA[%d] = %d \n", i, LA[i]);
   }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

当我们编译并执行上述程序时,它会产生以下结果 -

输出

The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

2.动态规划

动态编程方法类似于将问题分解为更小但更小的子问题的分而治之。但不同的是,分而治之,这些子问题并没有独立解决。相反,记住这些较小子问题的结果并用于类似或重叠的子问题。

动态编程用于我们遇到问题的地方,可以将其划分为类似的子问题,以便可以重复使用它们的结果。大多数情况下,这些算法用于优化。在解决现有子问题之前,动态算法将尝试检查先前解决的子问题的结果。结合子问题的解决方案以实现最佳解决方案。

所以我们可以说 -

  • 该问题应该能够分成较小的重叠子问题。
  • 通过使用较小子问题的最佳解决方案可以实现最佳解决方案。
  • 动态算法使用Memoization。

对照

与解决局部优化的贪婪算法相反,动态算法被激励用于问题的整体优化。

与分而治之的算法相比,其中解决方案被组合以实现整体解决方案,动态算法使用较小子问题的输出,然后尝试优化更大的子问题。动态算法使用Memoization来记住已经解决的子问题的输出。

实例1

使用动态编程方法可以解决以下计算机问题 -

  • 斐波纳契数系列
  • 背包问题
  • 河内塔
  • 由Floyd-Warshall完成的所有最短路径
  • Dijkstra的最短路径
  • 项目安排

动态编程可以自上而下和自下而上的方式使用。当然,大多数情况下,参考之前的解决方案输出比CPU周期重新计算更便宜。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/465132
推荐阅读
相关标签
  

闽ICP备14008679号