在二元编号的圆中仅使用1的正多边形-yiteyi-C++库

给定一个二进制整数数组，假设这些值在圆周上保持相等距离。我们需要知道是否有可能只使用1作为其顶点绘制正多边形，如果有可能，则打印正多边形的最大边数。 例子：

null

Input : arr[] = [1, 1, 1, 0, 1, 0]Output : Polygon possible with side length 3We can draw a regular triangle having 1s as its vertices as shown in below diagram (a).Input : arr[] = [1, 0, 1, 0, 1, 0, 1, 0, 1, 1]Output : Polygon possible with side length 5We can draw a regular pentagon having 1s as its vertices as shown in below diagram (b).

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

我们可以通过得到一个可能的多边形可以拥有的顶点数和数组中的值总数之间的关系来解决这个问题。假设圆中一个可能的正多边形有K个顶点或K条边，那么它应该满足两个条件才能得到答案，如果给定的数组大小是N，那么K应该分割N，否则K个顶点不能以相等的方式将N个顶点分割为正多边形。接下来，在所选多边形的每个顶点上都应该有一个。在以上几点之后，我们可以看到，为了解决这个问题，我们需要迭代N的除数，然后检查所选除数距离处数组的每个值是否为1。如果是1，那么我们找到了解决方案。我们只需从1迭代到sqrt（N），就可以在O（sqrt（N））时间内迭代所有的除数。你可以阅读更多关于这方面的内容在这里 .

C++

                         // C++ program to find whether a regular polygon                       
                         // is possible in circle with 1s as vertices                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // method returns true if polygon is possible with                       
                         // 'midpoints' number of midpoints                       
                         bool                                     checkPolygonWithMidpoints(                                     int                                     arr[],                                     int                                     N,                       
                                                 int                                     midpoints)                       
                         {                       
                                                 // loop for getting first vertex of polygon                       
                                                 for                                     (                                     int                                     j = 0; j < midpoints; j++)                       
                                                 {                       
                                                 int                                     val = 1;                       
           
                                                 // loop over array values at 'midpoints' distance                       
                                                 for                                     (                                     int                                     k = j; k < N; k += midpoints)                       
                                                 {                       
                                                 // and(&) all those values, if even one of                       
                                                 // them is 0, val will be 0                       
                                                 val &= arr[k];                       
                                                 }                       
           
                                                 /*  if val is still 1 and (N/midpoints) or (number                       
                                                 of vertices) are more than two (for a polygon                       
                                                 minimum) print result and return true */                       
                                                 if                                     (val && N/midpoints > 2)                       
                                                 {                       
                                                 cout <<                                     "Polygon possible with side length "                                     <<                       
                                                 << (N/midpoints) << endl;                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         // method prints sides in the polygon or print not                       
                         // possible in case of no possible polygon                       
                         void                                     isPolygonPossible(                                     int                                     arr[],                                     int                                     N)                       
                         {                       
                                                 //  limit for iterating over divisors                       
                                                 int                                     limit =                                     sqrt                                     (N);                       
                                                 for                                     (                                     int                                     i = 1; i <= limit; i++)                       
                                                 {                       
                                                 // If i divides N then i and (N/i) will                       
                                                 // be divisors                       
                                                 if                                     (N % i == 0)                       
                                                 {                       
                                                 //  check polygon for both divisors                       
                                                 if                                     (checkPolygonWithMidpoints(arr, N, i) ||                       
                                                 checkPolygonWithMidpoints(arr, N, (N/i)))                       
                                                 return                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 cout <<                                     "Not possiblen"                                     ;                       
                         }                       
           
                         // Driver code to test above methods                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 1};                       
                                                 int                                     N =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 isPolygonPossible(arr, N);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find whether a regular polygon                       
                         // is possible in circle with 1s as vertices                       
           
                         class                                     Test                       
                         {                       
                                                 // method returns true if polygon is possible with                       
                                                 // 'midpoints' number of midpoints                       
                                                 static                                     boolean                                     checkPolygonWithMidpoints(                                     int                                     arr[],                                     int                                     N,                       
                                                 int                                     midpoints)                       
                                                 {                       
                                                 // loop for getting first vertex of polygon                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < midpoints; j++)                       
                                                 {                       
                                                 int                                     val =                                     1                                     ;                       
                                   
                                                 // loop over array values at 'midpoints' distance                       
                                                 for                                     (                                     int                                     k = j; k < N; k += midpoints)                       
                                                 {                       
                                                 // and(&) all those values, if even one of                       
                                                 // them is 0, val will be 0                       
                                                 val &= arr[k];                       
                                                 }                       
                                   
                                                 /*  if val is still 1 and (N/midpoints) or (number                       
                                                 of vertices) are more than two (for a polygon                       
                                                 minimum) print result and return true */                       
                                                 if                                     (val !=                                     0                                     && N/midpoints >                                     2                                     )                       
                                                 {                       
                                                 System.out.println(                                     "Polygon possible with side length "                                     +                       
                                                 N/midpoints);                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // method prints sides in the polygon or print not                       
                                                 // possible in case of no possible polygon                       
                                                 static                                     void                                     isPolygonPossible(                                     int                                     arr[],                                     int                                     N)                       
                                                 {                       
                                                 //  limit for iterating over divisors                       
                                                 int                                     limit = (                                     int                                     )Math.sqrt(N);                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= limit; i++)                       
                                                 {                       
                                                 // If i divides N then i and (N/i) will                       
                                                 // be divisors                       
                                                 if                                     (N % i ==                                     0                                     )                       
                                                 {                       
                                                 //  check polygon for both divisors                       
                                                 if                                     (checkPolygonWithMidpoints(arr, N, i) ||                       
                                                 checkPolygonWithMidpoints(arr, N, (N/i)))                       
                                                 return                                     ;                       
                                                 }                       
                                                 }                       
                                   
                                                 System.out.println(                                     "Not possible"                                     );                       
                                                 }                       
                                   
                                                 // Driver method                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     arr[] = {                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     1                                     };                       
           
                                                 isPolygonPossible(arr, arr.length);                       
                                                 }                       
                         }                       

Python3

                         # Python3 program to find whether a                       
                         # regular polygon is possible in circle                       
                         # with 1s as vertices                       
                         from                                     math                                     import                                     sqrt                       
           
                         # method returns true if polygon is                       
                         # possible with 'midpoints' number                       
                         # of midpoints                       
                         def                                     checkPolygonWithMidpoints(arr, N, midpoints) :                       
           
                                                 # loop for getting first vertex of polygon                       
                                                 for                                     j                                     in                                     range                                     (midpoints) :                       
                                   
                                                 val                                     =                                     1                       
           
                                                 # loop over array values at                       
                                                 # 'midpoints' distance                       
                                                 for                                     k                                     in                                     range                                     (j , N, midpoints) :                       
                                   
                                                 # and(&) all those values, if even                       
                                                 # one of them is 0, val will be 0                       
                                                 val &                                     =                                     arr[k]                       
                                   
                                                 # if val is still 1 and (N/midpoints) or (number                       
                                                 # of vertices) are more than two (for a polygon                       
                                                 # minimum) print result and return true                       
                                                 if                                     (val                                     and                                     N                                     /                                     /                                     midpoints >                                     2                                     ) :                       
                                   
                                                 print                                     (                                     "Polygon possible with side length"                                     ,                       
                                                 (N                                     /                                     /                                     midpoints))                       
                                                 return                                     True                       
                                   
                                                 return                                     False                       
           
                         # method prints sides in the polygon or print                       
                         # not possible in case of no possible polygon                       
                         def                                     isPolygonPossible(arr, N) :                       
           
                                                 # limit for iterating over divisors                       
                                                 limit                                     =                                     sqrt(N)                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,                                     int                                     (limit)                                     +                                     1                                     ) :                       
                                   
                                                 # If i divides N then i and (N/i)                       
                                                 # will be divisors                       
                                                 if                                     (N                                     %                                     i                                     =                                     =                                     0                                     ) :                       
                                   
                                                 # check polygon for both divisors                       
                                                 if                                     (checkPolygonWithMidpoints(arr, N, i)                                     or                       
                                                 checkPolygonWithMidpoints(arr, N, (N                                     /                                     /                                     i))):                       
                                                 return                       
                                   
                                                 print                                     (                                     "Not possiblen"                                     )                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 arr                                     =                                     [                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     0                                     ,                                     1                                     ,                                     1                                     ]                       
                                                 N                                     =                                     len                                     (arr)                       
                                                 isPolygonPossible(arr, N)                       
           
                         # This code is contributed by Ryuga                       

C#

                         // C# program to find whether                       
                         // a regular polygon is possible                       
                         // in circle with 1s as vertices                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // method returns true if                       
                         // polygon is possible                       
                         // with 'midpoints' number                       
                         // of midpoints                       
                         static                                     bool                                     checkPolygonWithMidpoints(                                     int                                     []arr,                                     int                                     N,                       
                                                 int                                     midpoints)                       
                         {                       
                                                 // loop for getting first                       
                                                 // vertex of polygon                       
                                                 for                                     (                                     int                                     j = 0; j < midpoints; j++)                       
                                                 {                       
                                                 int                                     val = 1;                       
           
                                                 // loop over array values                       
                                                 // at 'midpoints' distance                       
                                                 for                                     (                                     int                                     k = j; k < N; k += midpoints)                       
                                                 {                       
                                                 // and(&) all those values,                       
                                                 // if even one of them is 0,                       
                                                 // val will be 0                       
                                                 val &= arr[k];                       
                                                 }                       
           
                                                 /* if val is still 1 and                       
                                                 (N/midpoints) or (number                       
                                                 of vertices) are more than                       
                                                 two (for a polygon minimum)                       
                                                 print result and return true */                       
                                                 if                                     (val != 0 && N / midpoints > 2)                       
                                                 {                       
                                                 Console.WriteLine(                                     "Polygon possible with "                                     +                       
                                                 "side length "                                     +                       
                                                 N / midpoints);                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         // method prints sides in the                       
                         // polygon or print not possible                       
                         // in case of no possible polygon                       
                         static                                     void                                     isPolygonPossible(                                     int                                     []arr,                       
                                                 int                                     N)                       
                         {                       
                                                 // limit for iterating                       
                                                 // over divisors                       
                                                 int                                     limit = (                                     int                                     )Math.Sqrt(N);                       
                                                 for                                     (                                     int                                     i = 1; i <= limit; i++)                       
                                                 {                       
                                                 // If i divides N then i                       
                                                 // and (N/i) will be divisors                       
                                                 if                                     (N % i == 0)                       
                                                 {                       
                                                 // check polygon for                       
                                                 // both divisors                       
                                                 if                                     (checkPolygonWithMidpoints(arr, N, i) ||                       
                                                 checkPolygonWithMidpoints(arr, N, (N / i)))                       
                                                 return                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 Console.WriteLine(                                     "Not possible"                                     );                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 int                                     []arr = {1, 0, 1, 0, 1,                       
                                                 0, 1, 0, 1, 1};                       
           
                                                 isPolygonPossible(arr, arr.Length);                       
                         }                       
                         }                       
           
                         // This code is contributed by jit_t                       

PHP

                         <?php                       
                         // PHP program to find whether                       
                         // a regular polygon is possible                       
                         // in circle with 1s as vertices                       
                         // method returns true if polygon                       
                         // is possible with 'midpoints'                       
                         // number of midpoints                       
           
                         function                                     checkPolygonWithMidpoints(                                     $arr                                     ,                                     $N                                     ,                       
                                                 $midpoints                                     )                       
                         {                       
                                                 // loop for getting first                       
                                                 // vertex of polygon                       
                                                 for                                     (                                     $j                                     = 0;                                     $j                                     <                                     $midpoints                                     ;                                     $j                                     ++)                       
                                                 {                       
                                                 $val                                     = 1;                       
           
                                                 // loop over array values                       
                                                 // at 'midpoints' distance                       
                                                 for                                     (                                     $k                                     =                                     $j                                     ;                                     $k                                     <                                     $N                                     ;                                     $k                                     +=                                     $midpoints                                     )                       
                                                 {                       
                                                 // and(&) all those values,                       
                                                 // if even one of them is 0,                       
                                                 // val will be 0                       
                                                 $val                                     &=                                     $arr                                     [                                     $k                                     ];                       
                                                 }                       
           
                                                 /* if val is still 1 and                       
                                                 (N/midpoints) or (number                       
                                                 of vertices) are more than                       
                                                 two (for a polygon minimum)                       
                                                 print result and return true */                       
                                                 if                                     (                                     $val                                     &&                                     $N                                     /                                     $midpoints                                     > 2)                       
                                                 {                       
                                                 echo                                     "Polygon possible with side length "                                     ,                       
                                                 (                                     $N                                     /                                     $midpoints                                     ) ,                                     ""                                     ;                       
                                                 return                                     true;                       
                                                 }                       
                                                 }                       
                                                 return                                     false;                       
                         }                       
           
                         // method prints sides in                       
                         // the polygon or print not                       
                         // possible in case of no                       
                         // possible polygon                       
                         function                                     isPolygonPossible(                                     $arr                                     ,                                     $N                                     )                       
                         {                       
                                                 // limit for iterating                       
                                                 // over divisors                       
                                                 $limit                                     = sqrt(                                     $N                                     );                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $limit                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // If i divides N then                       
                                                 // i and (N/i) will be                       
                                                 // divisors                       
                                                 if                                     (                                     $N                                     %                                     $i                                     == 0)                       
                                                 {                       
                                                 // check polygon for                       
                                                 // both divisors                       
                                                 if                                     (checkPolygonWithMidpoints(                                     $arr                                     ,                                     $N                                     ,                                     $i                                     ) ||                       
                                                 checkPolygonWithMidpoints(                                     $arr                                     ,                                     $N                                     , (                                     $N                                     /                                     $i                                     )))                       
                                                 return                                     ;                       
                                                 }                       
                                                 }                       
           
                         echo                                     "Not possiblen"                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 0, 1, 0, 1,                       
                                                 0, 1, 0, 1, 1);                       
                         $N                                     = sizeof(                                     $arr                                     );                       
                         isPolygonPossible(                                     $arr                                     ,                                     $N                                     );                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to                       
                         // find whether a regular polygon                       
                         // is possible in circle with 1s as vertices                       
           
                         // method returns true if polygon is possible with                       
                         // 'midpoints' number of midpoints                       
                         function                                     checkPolygonWithMidpoints(arr, N, midpoints)                       
                         {                       
                                                 // loop for getting first vertex of polygon                       
                                                 for                                     (let j = 0; j < midpoints; j++)                       
                                                 {                       
                                                 let val = 1;                       
           
                                                 // loop over array values at                       
                                                 // 'midpoints' distance                       
                                                 for                                     (let k = j; k < N; k += midpoints)                       
                                                 {                       
                                                 // and(&) all those values,                       
                                                 // if even one of                       
                                                 // them is 0, val will be 0                       
                                                 val &= arr[k];                       
                                                 }                       
           
                                                 /*  if val is still 1 and                       
                                                 (N/midpoints) or (number                       
                                                 of vertices) are more than                       
                                                 two (for a polygon                       
                                                 minimum) print result and return true */                       
                                                 if                                     (val && parseInt(N/midpoints) > 2)                       
                                                 {                       
                                                 document.write(                       
                                                 "Polygon possible with side length "                                     +                       
                                                 parseInt(N/midpoints) +                                     "<br>"                       
                                                 );                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         // method prints sides in the polygon or print not                       
                         // possible in case of no possible polygon                       
                         function                                     isPolygonPossible(arr, N)                       
                         {                       
                                                 //  limit for iterating over divisors                       
                                                 let limit = Math.sqrt(N);                       
                                                 for                                     (let i = 1; i <= limit; i++)                       
                                                 {                       
                                                 // If i divides N then i and (N/i) will                       
                                                 // be divisors                       
                                                 if                                     (N % i == 0)                       
                                                 {                       
                                                 //  check polygon for both divisors                       
                                                 if                                     (checkPolygonWithMidpoints(arr, N, i) ||                       
                                                 checkPolygonWithMidpoints(arr, N,                       
                                                 parseInt(N/i)))                       
                                                 return                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 document.write(                                     "Not possible"                                     );                       
                         }                       
           
                         // Driver code to test above methods                       
                                                 let arr = [1, 0, 1, 0, 1, 0, 1, 0, 1, 1];                       
                                                 let N = arr.length;                       
                                                 isPolygonPossible(arr, N);                       
           
                         </script>                       

输出：

Polygon possible with side length 5

本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章