我一直在解决一个需要约瑟夫斯问题和大量素数的问题......
这是我的代码...
/*
josephus problem.uri judge:1030
author :: R_H_T
*/
#include <stdio.h>
#include <stdlib.h>
int count;
//int *c = &count;
typedef struct node{ // make a a linked list structure node with a number,next node and previous node
int number;
struct node *next;
struct node *previous;
} node;
node* create (int n){ //create nodes
node *nd = malloc(sizeof(node));
nd->number = n;
nd->next = NULL;
nd->previous = NULL;
return nd;
}
void kill(node *n){ // set node.numbers = 0
n->number = 0;
//free(n);
}
node* next_node(node *n,int step){ // decide next node location by stepsize
if (step == 1)
{
//count = 0;
return n;
}
next_node(n->next,(step-1));
}
void setvalue(int array_copy[], int i, int n)
{
int j,p;
for(j = 2; (i*j) <= n ; j++)
{
p = i*j;
array_copy[p] = 1;
}
}
int main(){
//freopen("in.txt","r",stdin);
node *current,*update_next,*head,*temp;
int i,k,human_c,j=0,flag=0;
//scanf("%d",&testcase); // input testcases
//start prime number selection by algo -> Sieve of Eratosthenes
int n,l=0;
//scanf("%i",&n);
n=3502;
int prime_array[1000];
int array[n];
for (i = 1; i <= n; i++) // initialize all value of the array to 0
{
array[i] = 0;
}
for( i = 2; i < n; i++)
{
setvalue(array,i,n); // set value 0 to its muliple cases
}
for(i = 2; i <= n; i++)
{
if(array[i] == 0) // find the value which is 0 and record it in an array naming prime_array[]
{
//printf("%i ",i );
prime_array[l] = i;
l++;
}
}
/*for ( i = 0; i <= l ; i++)
{
printf("%in",prime_array[i] );
} */
// end prime number selection
for( k = 1;; k++ )
{
//scanf("%i",&num_state);
scanf("%i",&human_c); // scan the number of nodes
/*if(num_state < 13 || num_state > 100) // limit is 13 <= N <= 100
return 1;
if(num_state == 13) // state 13 gives 1...we knew that so we didn't compute
{
printf("%in",1 );
continue;
}*/
if(human_c == 0) // a'0' input finishes it
return 0;
//count = 0;
node *first_node = create(1); // create first node with node.number 1
node *last_node = create(human_c); // create last node with node.number = number of people
node *a[human_c]; // decare a node type array
a[0]=NULL; // keep a[0] out of it
a[1] = first_node; // assign a[1] the first node
a[human_c] = last_node; // assign a[number of people] the last node
a[1]->previous = last_node; // link a[1] with previous
a[human_c]->next = first_node; // link a[number of people] with the first node
for(i = 2; i < human_c;i++){ // create nodes from 2 to (number of people-1)
a[i] = create(i);
}
for(i= 2; i < human_c;i++){ //assign previous and next nodes for 2 to (number of people-1)
a[i]->next = a[i+1] ;
a[i]->previous = a[i-1];
}
a[1]->next = a[2]; //link a[1] with next node a[2]
a[human_c]->previous = a[human_c-1]; //link (last node)a[number of people] with the previous a[number of people-1]
head = a[1]; //assign head or start position
flag = 0;
i = 0; //set flag for the first node
do{
if (flag == 0)
{
current = next_node(head,prime_array[i]); // evaluate next position for head node or start node only saving in "current" node
temp = current->previous; // keep the previous node for manipulation
temp->next = current->next; // set node.next for the previous node to the next of the current node
update_next = current->next; // keep the next node for manipulationk
update_next->previous = temp; // set node.previous for the next node which is update_next to the address of the previous of the current node which is temp
//head->next = current -> next;
flag = 1;
i++;
}
else
{
current = next_node(update_next,prime_array[i]); // evaluate next position for rest of the nodes
temp = current->previous; // keep the previous node for manipulation
temp->next = current->next; // set node.next for the previous node to the next of the current node
update_next = current->next; // keep the next node for manipulationk
update_next->previous = temp; // set node.previous for the next node which is update_next to the address of the previous of the current node which is temp
//update_next->next = current->next;
i++;
}
//update_next->previous = current->previous;
kill(current); // kill the newly found position
count++; // take a record of the total kill
//node *current = next_node(update_next,step_c);
}while((human_c-count) > 1); // keep the killing spree unit there is only one person left
for ( i = 1; i <= human_c; i++)
{
if(a[i]->number) // check if any node is alive which means anynode has a node.number higher than 0
{
//printf("Case %d: ",k );
printf("%in",a[i]->number );
}
}
for ( i = 1; i <= human_c; i++){ // free the allocated space on heap
free(a[i]);
}
count = 0; // set total kill to 0 as new testcase might start
}
return 0;
}
它适用于值 490，但它在 491 上给出分段错误..为什么会这样？
问题的链接是 https://www.urionlinejudge.com.br/judge/en/problems/view/1032
如果steps不等于 1，next_node() 则不返回任何值。
顺便说一句，您的编译器可能已经警告过您。
main() 和 setvalue() 中的索引超出了 array[] 的界限
void setvalue(int array_copy[], int i, int n)
{
...
for(j = 2; (i*j) <= n ; j++)
{
p = i*j;
array_copy[p] = 1; // ERROR: out of bounds when (i*j) == n
}
}
int main()
{
...
n=3502;
...
int array[n];
...
for (i = 1; i <= n; i++)
{
array[i] = 0; // ERROR: out of bounds when i == n
}
for( i = 2; i < n; i++)
{
setvalue(array,i,n);
}
for(i = 2; i <= n; i++)
{
if(array[i] == 0) // ERROR: out of bounds when i == n
...
}