贪心算法 导学案-2021-2022学年高中信息技术浙教版选修1

| 6页
| 574人阅读
| 96人下载
普通

高二信息技术导学案    VB模块   班级            姓名               

《贪心算法》导学案

[考试要求]

1.贪心算法       (c)

 [学习目标]

1.  掌握贪心算法基本思想。

2.  使用贪心算法思想解决实际问题。   

[自主学习]

一、 知识梳理

1.贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的             。

二、自我检测

1. 小王玩一个删数游戏,将一个正整数删去其中n位数字,要求在保证余下的数字不改变顺序的情况下尽可能小。例如,数字54632,删去2位数字后,能得到的最小的数字为432。小明的想法是每次删一位效字,使得每次删后产生的新数字是最小的,删n次后得到最终结果,所以将数字从左往右数,找到第一个降序数列,将数列的第一位数删去即可,如数字54632,第一个降序数列为5、4,删去5,得到4632,再次找到第一个降序数列6、3,删去数字6,得到432即为结果,运行效果如下,请完成填空。

(1)若数字为“178543”,要求删去4位,最终的数字为                          。

(2)实现上述功能的VB程序如下,请在划线处填入合适代码。

’函数Del()通过删除的数s和待删除数的位置i进行删除

Function Del(s as Integer)as String

If i = 1 then

   s = Mid(s, i+1,len(s)-1)

ElseIf i = Len(s) then

   s = Mid(s, 1,len(s)-1)

Else

      ①     

End If

Del = s

End Function

 

Private Sub Command1_Click( )

Dim s As String ,n As Integer, i As Integer, h As Integer

s = Text1.Text

n = Val(Text2.Text)

h = len(s)

For i = 1 To      ②    

   If Mid(s, i , 1)>Mid(s, i+1 , 1)  Then

          ③     

     n = n – 1page number 0


高二信息技术导学案    VB模块   班级            姓名               

     h = h – 1

     i = 0

  End if

  If n = 0 then Exit For

Next i

Label1.Caption = Str(s)

End Sub

[课堂练习]

1.最大整数问题:贪心算法中,有一类问题称为最大整数问题,问题的描述是:设有n个随机生成的正整数,将它们连接成一排,组成一最大的多位整数,其求解思想是:先把整数转换成字符串,然后在比较a+b和b-a,如果a十b>=a-b,就把a排在b的前面,反之则把a排在b的后面。例如:n=3时,3个整数13,12,343,连成的最大整数为34331213。

小王同学编写了一个VB程序,功能如下:

在列表框List1中随机生成n个1~1000之间的整数,单击“运行”按钮Command1后进行处理,最大整数结果输出在文本框Text1中,当n=4 时,程序运行界面如图所示。

VB程序如下,请回答下列问题:

(1)当n-3时,3个数:719,791,79,由这三个数组成的最大整数为             。

(2)请在划线处填入合适的代码。

Const n = 4

Dim a(l T0 10) As Integer

Private Sub Form Load()’函数CStr()和Str()功能类似,但输出字符时无前导空格

Randomize

For i = 1 To n

 a(i) =  ①        ’ 生成1~1000间的随机整数

  Listl.Addltem“a("+CStr(i)+“)=”+CStr(a(i))

Next i

End Sub

Function cmp(a As Integer, b As Inte-ger)As Boolean

   If CStr(a) +CStr(b) < CStr(b) +  CStr(a) Then

      cmp = True

Else

      cmp = False

End If

End Function

Private Sub Command1_Click()

Dim i As Integer, j As Integer, temp As Integer

Textl. Text =“”

For i = 1 To n - 1

   For j = n To i + 1 Step -1

     If    ②      Then

temp = a(j - 1)

a(j - 1)= a(j)

           ③     

     End If

  Next j

Next i

For i = 1 To npage number 1


高二信息技术导学案    VB模块   班级            姓名               

   Textl. Text = Textl. Text + CStr(a(i)

Next i

End Sub

[课后练习]

1.物品装袋问题。现有n个物品(不超过20个),及一个能装体积不超过v的袋子,分别给出各物品的体积及价值,求装入袋子里的物品价值总和的最大值。请编写VB程序,实现如下功能:在文本框Textl中输入袋子的体积,单击“计算”按钮Commandl,在文本框Text2中输出装入袋子里的物品价值总和的最大值,运行效果如图所示。

算法设计:为了便装入袋子的价值总和最大,首先应该把单位价值(该物品的价值÷体积)最大的物品全部放入袋子(如果袋子当前剩余的容量不小于该物品的体积),然后再放单位价值第二的物品,如此往复。当袋子剩余的容量装不下一个完整的物品时,可以将这个物品的部分(若干个单位体积)装入袋子,直到袋子装满。

VB程序如下,请回答下列问题:

(1)根据题意与算法描述,现有4个物品,其对应的体积和价值如上表所示,若袋子的体积为30,则装入袋子里的物品最大价值为                 (四舍五入保留1位小数)。

(2)请在划线处填入合适的代码。

Dim v(l T0 20) As Integer’每个物品体积

Dim w(l T0 20) As Integer’每个物品价值

Dim pw(l T0 20) As Double’依次存储每个物品的单位价值

Dim n As Integer’存储物品的总个数

Private Sub Form_Load()

’初始化操作,并将每个物品的体积和价值依次显示在列表框Listl中(代码略);

’将物品的个数存人变量n中;

’将每个物品的体积依次存人数组v(l)到v(n)中;

’将每个物品的价值依次存人数组w(l)到w(n)中;

End Sub

Sub Sort() ’根据每个物品的单位价值进行降序排序

For i =1 To n - 1

K= i

For j= j + 1 To n

     If  ①   Then k = j

Next j

If k <> i Then

    t=v(i):v(i)=v(k):v(k)=t

    t=w(i):w(i)=w(k):w(k)=t

    p=pw(i):pw(i)=pw(k):pw(k)=p

End If

Next i

End Subpage number 2


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。