Foxtable(狐表)用户栏目专家坐堂 → 凑数


  共有4036人关注过本帖树形打印复制链接

主题:凑数

帅哥哟,离线,有人找我吗?
keli0917
  1楼 | 信息 | 搜索 | 邮箱 | 主页 | UC


加好友 发短信
等级:童狐 帖子:296 积分:2789 威望:0 精华:0 注册:2018/5/21 16:49:00
凑数  发帖心情 Post By:2023/9/6 21:10:00 [只看该作者]

假设有一组数1,2,5,9,1,0,4,5,从中选N个数,凑成10。
例出所有的分组。
帮忙完善一下,递归真的不懂。

'递归函数,用于数组中寻找N项之和等于目标值的组合
Dim str As String = args(0) '原始数组
Dim nums() As String = str.Split(",") '将str内容拆分成数组
Array.Sort(nums)
Dim target As Decimal=args(1) '目标值
Dim n As Integer= args(2) 'N项,N张fa piao号码
Dim StartIndex As Integer = args(3) '一般为0

Dim sum As Decimal
Dim result() As Decimal
'当n=2时,转为寻找两项之和等于目标值的问题
If n = 2 Then
    Dim left As Integer = StartIndex '左指针从STRARTINDEX开始
    Dim right As Integer = nums.length - 1
    '使用双指针法搜索满足条件的组合
    Do While left < right
        sum = val(nums(left)) + val(nums(right))
'MessageBox.Show(nums(left))
'MessageBox.Show(nums(right))
      '  MessageBox.Show("sum:="&sum)
       ' MessageBox.Show("target:="&target)
        If sum = target Then
            result = New Decimal() {nums(left),nums(right)}'找到一组解,加入结果数组
            messagebox.Show(result(0))
            messagebox.Show(result(1))

            left = left +1
            right = right - 1
            '跳过重复的元数
            Do While left < right And nums(left) = nums(left - 1)
                left = left +1
            Loop
            Do While left < right And nums(right) = nums(right + 1)
                right = right - 1
            Loop
            '跳过重复的元数 end
        ElseIf sum < target Then
            left = left +1
        Else
            right = right -1
            
        End If
    Loop
Else
    '当N不等于2时,使用递归寻找N-1项之和等于targe 减去当前项的组合
    Dim i As Integer
    For i = startindex To nums.length - n + 1
        If i = startindex Or nums(i) <> nums(i-1) Then
            Functions.Execute("N个数和等于M",nums,target - nums(i),n-1,i+1)
        End If
    Next
End If


 回到顶部
帅哥哟,离线,有人找我吗?
有点蓝
  2楼 | 信息 | 搜索 | 邮箱 | 主页 | UC


加好友 发短信
等级:超级版主 帖子:111381 积分:566969 威望:0 精华:9 注册:2015/6/24 9:21:00
  发帖心情 Post By:2023/9/7 13:08:00 [只看该作者]

函数,假设名称为child

Dim ss() As Integer = Args(0) '原数组
Dim target As Integer = Args(1) '结果和
Dim currentSum As Integer = Args(2) '累加和
Dim idx As Integer = Args(3) '开始索引
Dim n As Integer = Args(4) '遍历层次。或者叫做取数个数,比如任意取2个数字的和为10,表示n是2;任意取3个数字的和为10,表示n是3
Dim lst As List(Of Integer) = Args(5) '参与计算的数组集合
Dim res As List(Of List(Of Integer)) = Args(6) '结果
If n = 1 Then '表示是已经取的最后一个数字
    For i As Integer = idx + 1 To ss.Length - 1 '遍历最后一个数字
        If currentSum + ss(i) = target Then '如果和之前的数字累加为10
            Dim lst3 As New List(Of Integer)
            lst3.AddRange(lst)
            lst3.Add(ss(i)) 
            res.Add(lst3) '添加到结果中
        End If 
    Next
Else '还不是最后一个数字
    For i As Integer = idx + 1 To ss.Length - 1
        Dim lst2 As New List(Of Integer) '新增一个集合,避免重复添加
        lst2.AddRange(lst) '添加之前的数字
        lst2.Add(ss(i)) '添加新的数字
        Functions.Execute("child", ss, target, currentSum + ss(i), i, n - 1, lst2, res) ‘继续计算下一层数字
    Next
End If

调用
Dim ss As Integer() = {1, 2, 5, 9, 1, 0, 4, 5} 
Dim target As Integer = 10
Dim res As New List(Of List(Of Integer))
Dim lst As List(Of Integer)
For n As Integer = 2 To ss.Length - 1
    lst = New List(Of Integer)
    Functions.Execute("child", ss, target, 0, - 1, n, lst, res)
Next 

'显示结果
For Each re As List(Of Integer) In res 
    Output.Show(String.Join(", ", re)) 
Next
[此贴子已经被作者于2024/9/29 10:10:32编辑过]

 回到顶部
帅哥哟,离线,有人找我吗?
keli0917
  3楼 | 信息 | 搜索 | 邮箱 | 主页 | UC


加好友 发短信
等级:童狐 帖子:296 积分:2789 威望:0 精华:0 注册:2018/5/21 16:49:00
  发帖心情 Post By:2024/9/28 21:51:00 [只看该作者]

Dim ss As Integer() = {1, 9, 9} 
Dim ss As Integer() = {1, 9, 9,9} 
————————
当SS为上面的组合时,上面函数会出错,可以帮忙修改一下吗
[此贴子已经被作者于2024/9/28 21:54:33编辑过]

 回到顶部
帅哥哟,离线,有人找我吗?
有点蓝
  4楼 | 信息 | 搜索 | 邮箱 | 主页 | UC


加好友 发短信
等级:超级版主 帖子:111381 积分:566969 威望:0 精华:9 注册:2015/6/24 9:21:00
  发帖心情 Post By:2024/9/29 10:10:00 [只看该作者]

函数改为

Dim ss() As Integer = Args(0) '原数组
Dim target As Integer = Args(1) '结果和
Dim currentSum As Integer = Args(2) '累加和
Dim idx As Integer = Args(3) '开始索引
Dim n As Integer = Args(4) '遍历层次。或者叫做取数个数,比如任意取2个数字的和为10,表示n是2;任意取3个数字的和为10,表示n是3
Dim lst As List(Of Integer) = Args(5) '参与计算的数组集合
Dim res As List(Of List(Of Integer)) = Args(6) '结果
'Dim f As String = Date.Now.ToString("mm:ss.ffff")
'Output.Show("idx=" & idx & ",n=" & n & ",currentSum=" & currentSum & ",------: " & f)
If n = 1 Then '表示是已经取的最后一个数字
    For i As Integer = idx + 1 To ss.Length - 1 '遍历最后一个数字
        If currentSum + ss(i) = target Then '如果和之前的数字累加为10
            Dim lst3 As New List(Of Integer)
            lst3.AddRange(lst)
            lst3.Add(ss(i)) 
            res.Add(lst3) '添加到结果中
        End If 
    Next
Else '还不是最后一个数字
'    Output.Show("lst.Count=" & lst.Count)
    For i As Integer = idx + 1 To ss.Length - 1
        Dim lst2 As New List(Of Integer) '新增一个集合,避免重复添加
        lst2.AddRange(lst) '添加之前的数字
        lst2.Add(ss(i)) '添加新的数字
        Functions.Execute("child", ss, target, currentSum + ss(i), i, n - 1, lst2, res) '继续计算下一层数字
    Next
End If
'Output.Show("------end: " & f)

 回到顶部