algorithm - 如何检查数字是否从给定数字生成

Question

给我一​​组1-360之间的数字。另一个数字 n 也给了我。我必须告诉我是否可以通过上面的数字列表生成给定的数字 n。我可以对给定的数字进行以下操作

1. (a+b)mod 360
2. (a-b)mod 360 其中 a>b
3. 我可以任意多次取一个数(即使是 a+b，a=b)

现在的目标是检测我是否可以生成数字 n

例如假设 n 是 60，给定的数字列表只有 100(但可能更多)，所以我可以通过将 100 加十五次来生成 60，然后取等于 60 的 mod360。

以下是我尝试过的解决方案

#include<stdio.h>
int ispossible=0;
void AnglePossible(int a1[],int angle,int currentangle,int n)
{
    int i;
    if(angle==(currentangle%360))
        ispossible = 1;
    else if((currentangle!=0)&&(currentangle%360==0))
        return;
    for(int i=0;i<n;i++)
    {
        AnglePossible(a1,angle,currentangle+a1[i],n);
    }
}

int main()
{
    int n,k;
    int a1[361],a2[361];
    int i,j;
    int result;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++)
        scanf("%d",&a1[i]);
    for(i=0;i<k;i++)
        scanf("%d",&a2[i]);

    for(i=0;i<k;i++)
    {
        ispossible=0;
        AnglePossible(a1,a2[i],0,n);
        if(ispossible==1)
        printf("YES\n");
        else
        printf("NO\n");
    }
    return 0;
}

Answer 1

这是解决(我认为)这个问题的一种朴素算法，但可能不是最有效的算法。

问题设置:

输入:

1. nums(数字。整数数组)
2. target(目标)

输出:

• 指示目标是否可达的 bool 值

本质上，您希望通过使用 nums 来达到目标。您的起点是数轴上的 0(您始终可以到达 0)。

因此，您会跟踪可以到达的位置(一个初始化为 [0] 的数组)。对于 nums 中的每个号码，您可以使用这个新号码更新您可以到达的位置。由于加法和减法是可交换的，因此顺序并不重要。

这是一个展示这个想法的小 Python 程序:

def reachable(i, start = 0): 
  cantReach = range(360)
  canReach = set()
  reach = start
  while reach in cantReach:
    cantReach.remove(reach)
    canReach.add(reach)
    reach += i
    reach = reach % 360 
  return canReach

def main(nums, target):
  canReach = set([0])
  for i in nums:
    for j in canReach:
      canReach = canReach.union(reachable(i, j)) 

  canReach = sorted(list(canReach))
  print "can reach:", canReach
  print "result:", target in canReach


main([100],60)

输出是:

can reach: [0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300, 320, 340]
result: True