一个1-360之间的一组数字，是给我。一个又一个数n，也给了我。我要告诉我是否可以生成给定的数n由一些上面的列表。我可以做下面给定的数字运算

（A + B）MOD 360 （A-B）模360，在A> B 我可以采取一个数字任意数量的时间（即使是在A + B，A = B）

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

实施例假设n是60及数给出的清单中的只是100（但也可以是更多个），所以我可以通过添加100 15时生成60，然后采取mod360它等于60。

下面是解决方案，我试图

 ＃包括＆LT; stdio.h中＆GT;
INT ispossible = 0;
无效AnglePossible（INT A1 []，诠释角度，诠释currentAngle中，INT N）
{
    INT I;
    如果（角==（currentAngle中360％））
        ispossible = 1;
    否则如果（（currentAngle中= 0）及！及（currentAngle中360％== 0））
        返回;
    的for（int i = 0;我n种;我++）
    {
        AnglePossible（A1，角度，currentAngle中+ A1 [I]中，n）;
    }
}

诠释的main（）
{
    诠释N，K;
    INT A1 [361]，A2 [361];
    INT I，J;
    INT结果;
    scanf函数（％D，和放大器; N，功放; K）;
    对于（I = 0; I＆n种;我+ +）
        scanf函数（％d个，和放大器; A1 [I]）;
    对于（i = 0; I＆LT; k;我++）
        scanf函数（％d个，和放大器; A2 [I]）;

    对于（i = 0; I＆LT; k;我++）
    {
        ispossible = 0;
        AnglePossible（A1，A2 [I]，0，n）的;
        如果（ispossible == 1）
        的printf（是\ N）;
        其他
        的printf（NO \ N）;
    }
    返回0;
}
 

解决方案

下面是一个天真的算法，解决了（我觉得）这个问题，但可能不是最有效的。

问题设置：

输入：

NUMS （数字。int数组） 目标（目标）

输出：

在布尔表示，如果目标可达

从本质上讲，你要使用的 NUMS ，以获得为目标。你的出发点是 0 在数轴上（你总是可以为 0 ）。

因此​​，您跟踪的位置，你可以得到（初始化为的数组[0] ）。对于 NUMS每个号码，您更新，你可以用这个新号码的位置。由于添加和substractions是可交换的，则顺序并不重要。

下面是一个小的Python程序显示出这样的想法：

 高清可达（一，启动= 0）：
  cantReach =范围（360）
  canReach =集（）
  到达=启动
  而达到cantReach：
    cantReach.remove（REACH）
    canReach.add（REACH）
    达到+ = I
    达到=达到360％
  返回canReach

高清主（NUMS，目标）：
  canReach =集（[0]）
  因为我在NUMS：
    对于j在canReach：
      canReach = canReach.union（可达（I，J））

  canReach =排序（表（canReach））
  打印可以达到，canReach
  打印的结果：，目标canReach


主（[100]，60）
 

的输出是：

 可以达到：[0，20，40，60，80，100，120，140，160，180，200，220，240，260，280，300，320， 340]
结果：真
 

A set of numbers between 1-360 is given to me. An another number n is also given to me. I have to tell whether I can generate the given number n by the above list of number. I can do following operations on the given numbers

(a+b)mod 360 (a-b)mod 360 where a>b I can take one number any number of time(even in a+b, a=b)

Now the goal is to detect whether I can generate the number n or not

Example suppose n is 60 and the list of number given is only 100(but it may be more), so i can generate 60 by adding 100 fifteen time and then take mod360 which is equal to 60.

Following is the solution that I have tried

#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;
}

解决方案

Here is a naive algorithm that solves(i think) this problem, but probably not the most efficient one.

Problem setup:

Input:

nums (numbers. an array of ints) target (the target)

Output:

bool indicating if target is reachable

Essentially you want to get to target by using nums. Your starting point is 0 on the number line (you can always get to 0).

Therefore, you keep track of the locations you can get to (an array initialized to [0]). For each number in nums, you update the locations that you can get to with this new number. Since additions and substractions are commutative, the order is not important.

Here is a small python program showing this idea:

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)

The output is:

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