API tools faq
paste
WhaleSpunk

Untitled

WhaleSpunk
May 19th, 2017
60
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 16.24 KB | None | 0 0
raw download clone embed print report
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5.  
  6. typedef struct node{
  7. int estado[6];
  8. int sequencia[6];
  9. int transicao_come_from;
  10. struct node *brother;
  11. struct node *son;
  12. struct node *father;
  13. }node;
  14.  
  15. node* create_node(int estado, int *sequencia,int transicao_come_from,int places);
  16. void add_son(node* father,node* new_son);
  17. void print(node* root,int places);
  18. node* checkSequence(node* atual, node* node, int num_places);
  19.  
  20.  
  21.  
  22. int main()
  23. {
  24. int places,transitions,check=1,flag=0;
  25. int i;
  26. int matriz_val[1000][3];
  27.  
  28. char teste[10],teste1[10],teste2[10];
  29. char state_inicial[20];
  30. int len, index=0,indice_matriz=0,indice_state=0;
  31. int matriz_state[6]={0};
  32.  
  33. struct node *head;
  34.  
  35. scanf("%d %d",&places, &transitions);
  36. int arrayTransitons[transitions][2][places];
  37. memset(arrayTransitons,0, sizeof(arrayTransitons));
  38. while(check==1){
  39.  
  40. if(flag==1){
  41.  
  42. for(i=0;i<places;i++){
  43. scanf("%s",&state_inicial);
  44. if(isdigit(state_inicial[0])){
  45. matriz_state[i]=atoi(state_inicial);
  46. //indice_state++;
  47. }
  48. }
  49.  
  50. check=0;
  51. }else{
  52. scanf("%s",&teste);
  53.  
  54. if(isdigit(teste[0])){
  55. scanf("%s %s",&teste1,&teste2);
  56. matriz_val[index][0]=atoi(teste);
  57. matriz_val[index][1]=atoi(teste1);
  58. matriz_val[index][2]=atoi(teste2);
  59. if(atoi(teste2) == 1){
  60. arrayTransitons[atoi(teste)-1][1][atoi(teste1)-1] = 1;
  61. }else{
  62. arrayTransitons[atoi(teste1)-1][0][atoi(teste)-1] = 1;
  63. }
  64.  
  65. index++;
  66. }else{
  67. //printf("flag=1\n");
  68. flag=1;
  69. }
  70.  
  71. }
  72.  
  73. }
  74.  
  75. printf("\n%d %d\n",places,transitions);
  76. for(i=0;i<index;i++){
  77. printf("%d %d %d\n",matriz_val[i][0],matriz_val[i][1],matriz_val[i][2]);
  78. }
  79. printf("STATE\n");
  80. for(i=0;i<places;i++){
  81. printf("%d ",matriz_state[i]);
  82. }
  83. printf("\n\n");
  84. int k,l;
  85. printf("[");
  86. for(i = 0; i<transitions; i++){
  87. printf("[");
  88. for(k =0;k<2;k++){
  89. printf("[");
  90. for(l = 0; l<places;l++){
  91. printf("%d, ", arrayTransitons[i][k][l]);
  92. }
  93. printf("],");
  94. }
  95. printf("],");
  96. }
  97. printf("]\n");
  98.  
  99. //considero aqui que do place 1 sair sempre o estado 1
  100. head=create_node(1,matriz_state,1,places);
  101. node * aux= head;
  102. while(addNextTransition(aux, transitions, places, arrayTransitons,head)){
  103. printf("\n-------------->AQUI");
  104. };
  105. printf("---------------------------------------------------PAI: ");
  106. for(i = 0; i<places; i++){
  107. printf("%d ", head->sequencia[i]);
  108. }
  109. printf("\n-------------------------------------------FILHO: ");
  110. for(i = 0; i<places; i++){
  111. printf("%d ", head->son->sequencia[i]);
  112. }
  113. while(addNextTransition(head->son, transitions, places, arrayTransitons, head) !=0);
  114. printf("\n----------------------------------------------FILHO FILHO: ");
  115. for(i = 0; i<places; i++){
  116. printf("%d ", head->son->son->sequencia[i]);
  117. }
  118. printf("\n-----------------------------------------FILHO FILHO IRMAO: ");
  119. for(i = 0; i<places; i++){
  120. printf("%d ", head->son->son->brother->sequencia[i]);
  121. }
  122. while(addNextTransition( head->son->son, transitions, places, arrayTransitons,head) !=0);
  123. printf("\n-------------------------------------FILHO FILHO FILHO: ");
  124. for(i = 0; i<places; i++){
  125. printf("%d ", head->son->son->son->sequencia[i]);
  126. }
  127. while(addNextTransition( head->son->son->son, transitions, places, arrayTransitons,head) !=0);
  128. printf("\n--------------------------------------FILHO FILHO FILHO FILHO: ");
  129. for(i = 0; i<places; i++){
  130. printf("%d ", head->son->son->son->son->sequencia[i]);
  131. }
  132. printf("\n-------------------------------------------FILHO FILHO FILHO FILHO IRMAO: ");
  133. for(i = 0; i<places; i++){
  134. printf("%d ", head->son->son->son->son->brother->sequencia[i]);
  135. }
  136. int check = 0;
  137. while(addNextTransition(aux,transitions,places,arrayTransitons) != 0){ //quanto tiver w talvez dê
  138. int i = 0;
  139.  
  140.  
  141. printf("OI + %d: ", i);
  142. for(i = 0; i<places; i++){
  143. printf("%d ", aux->sequencia[i]);
  144. }
  145.  
  146.  
  147. aux = aux->son;
  148.  
  149. if(aux->son == NULL){
  150. aux = aux->father;
  151. check = 1
  152. }
  153.  
  154.  
  155. }
  156. // memcpy(head->sequencia,matriz_state,sizeof(matriz_state));
  157. // head->estado=1;
  158. // head->transicao_come_from=1;
  159.  
  160.  
  161. //create_node(1,matriz_state,1,places);
  162. /*int num=1;//ja considero a transicao 1
  163. int atual=1;
  164. int first=0;
  165.  
  166. node* atual_node=head;
  167. node* aux_node=head;
  168. while(num<transitions){
  169. //vou ver por transicoes
  170. if(matriz_val[num][0]!=num){
  171.  
  172. }else{
  173. while(num==matriz_val[atual][0]){//mesma transicao
  174. if(first==0){
  175. //para verificar e garantir que a head começa no inicio da transicao 1
  176. if(matriz_val[atual][0]==1 && matriz_val[atual][2]==2){
  177. head->estado=matriz_val[atual][1];
  178. first=1;
  179. }
  180. }
  181. if(matriz_val[atual][2]==1){
  182. matriz_state[matriz_val[atual][1]-1]+=1;
  183.  
  184. }else if(matriz_val[atual][2]==2){
  185. matriz_state[matriz_val[atual][1]-1]-=1;
  186. }
  187.  
  188. if((matriz_val[atual][1]>matriz_val[atual][0])&&matriz_val[atual][2]==1){
  189. add_son(atual_node,create_node(matriz_val[atual][1],matriz_state,matriz_val[atual][0],places));
  190. }
  191.  
  192. atual++;
  193. }
  194. if(atual_node->brother!=NULL){
  195. atual_node=atual_node->brother;
  196. }else if(aux_node->son!=NULL){
  197. atual_node=aux_node->son;
  198. aux_node=aux_node->son;
  199. }else{
  200. break;
  201. }
  202.  
  203. }
  204.  
  205. num++;
  206. }*/
  207. //add_son(head,create_node(2,matriz_state,2,places));
  208. // printf("\nsequencia:\n");
  209. // for(i=0;i<places;i++){
  210. // printf("%d ",head->son->sequencia[i]);
  211. // }
  212. // printf("\nestado:\n");
  213. // printf("%d \n",head->son->estado);
  214. // printf("transicao:\n");
  215. // printf("%d \n",head->son->transicao_come_from);
  216. //
  217. // add_son(head,create_node(3,matriz_state,3,places));
  218. // printf("\n----brother---\nsequencia:\n");
  219. //
  220. /* printf("print\n");
  221. print(head,places, arrayTransitons, places);
  222.  
  223. printf("fim_print\n");*/
  224.  
  225. // for(i=0;i<places;i++){
  226. // printf("e1: %d \n",head->son->estado);
  227. // printf("s1: %d \n",head->son->sequencia[i]);
  228. // printf("e2: %d \n",head->son->brother->estado);
  229. // printf("s2: %d \n",head->son->brother->sequencia[i]);
  230. // }
  231. // printf("\nestado:\n");
  232. // printf("%d \n",head->son->brother->estado);
  233. // printf("transicao:\n");
  234. // printf("%d \n",head->son->brother->transicao_come_from);
  235.  
  236. return 0;
  237. }
  238.  
  239.  
  240.  
  241. void print_seq( int* seq,int places){
  242. int i;
  243. for(i=0;i<places;i++){
  244. printf("%d ",seq[i]);
  245.  
  246. }
  247. printf("\n");
  248. }
  249.  
  250. node* checkSequence(node* atual, node* node, int num_places){
  251. int i;
  252. printf("\nbeginCHECK_Sequence\n");
  253. print_seq(atual->sequencia,num_places);
  254.  
  255. print_seq(node->sequencia,num_places);
  256.  
  257.  
  258. for(i =0; i<num_places; i++){
  259. if((atual->sequencia[i] < node->sequencia[i]) && atual->sequencia[i] !=-1){
  260. //printf("\n-----------------------------------------------------É MAIOR2222222222222222222222222\n");
  261. printf("--------!!_-----atual: ");print_seq(atual->sequencia,num_places);
  262. printf("--------!!_-----node: ");print_seq(node->sequencia,num_places);
  263. atual->transicao_come_from = -99;
  264. return atual;
  265. }
  266. }
  267. printf("--->segue segundo teste\n");
  268. for(i = 0;i<num_places; i++){
  269.  
  270. if(atual->sequencia[i] > node->sequencia[i]){
  271. //printf("\n-----------------------------------------------------É MAIOR\n");
  272. atual->sequencia[i] = -1;
  273.  
  274. }
  275. }
  276. //print_seq(atual->sequencia,num_places);
  277. return atual;
  278.  
  279.  
  280. }
  281.  
  282. int search_node(node* atual, node* procurado, int places){
  283. int i;
  284. int flag = 1;
  285.  
  286. if(atual != NULL && procurado != NULL){
  287. // printf("\nAQUI---<\n");
  288. for(i=0;i<places;i++){
  289. /*printf("\nAQUI FOR---<\n");
  290. printf("\nSEQ1: %d ; SEQ2: %d", atual->sequencia[i], procurado->sequencia[i]);
  291. printf("\nAQUI FOR2---<\n");*/
  292. if(atual->sequencia[i] != procurado->sequencia[i]){
  293. //printf("\nAQUI IF---<\n");
  294. flag = 0;
  295. break;
  296. }
  297. }
  298.  
  299. if(flag == 0){
  300. if(atual->son != NULL){
  301. search_node(atual->son,procurado,places);
  302. //printf("\nAQUI DEPOIS1---<\n");
  303. }
  304. else{
  305. if(atual->brother !=NULL){
  306. search_node(atual->brother,procurado,places);
  307. //printf("\nAQUI DEPOIS2---<\n");
  308. }
  309. }
  310. }
  311. }
  312.  
  313. return flag;
  314. }
  315.  
  316.  
  317.  
  318.  
  319. node* create_node(int estado, int *sequencia,int transicao_come_from, int places){
  320.  
  321. int i;
  322. //printf("seq:\n");
  323. /*for(i=0;i<places;i++){
  324. printf("%d ",sequencia[i]);
  325. }*/
  326. node* new_node;
  327. new_node= (node *)malloc(sizeof(node));
  328. new_node->father = NULL;
  329. if(estado != -1){
  330. memset(new_node->estado, 0, sizeof(new_node->estado));
  331. new_node->estado[estado-1]=1;
  332.  
  333. for(i=0; i<places; i++){
  334. new_node->sequencia[i] = sequencia[i];
  335.  
  336. }
  337. new_node->transicao_come_from=transicao_come_from;
  338. //printf("\ncriou no\n\n");
  339. }
  340. return new_node;
  341.  
  342. }
  343. int addNextTransition(node* father, int num_transitions, int num_places, int arrayTransitions[num_transitions][2][num_places], node* root){
  344.  
  345. int i,j,k,p,s;
  346. int done=0;
  347. int sequencia_aux[6];
  348. int estado = get_estado(father, num_places);
  349. int finalState = 0;
  350.  
  351. printf("\n");
  352. printf("begin\n");
  353. if(estado != -1){
  354.  
  355. //printf("\nSEQUENCIA: ");
  356. for(i = 0; i<num_places;i++){
  357. sequencia_aux[i] = father->sequencia[i];
  358. printf("%d ", sequencia_aux[i]);
  359.  
  360. }
  361. printf("\tESTADO: %d\n", estado);
  362. done = 1;
  363. // printf("\nestado: %d\n", estado+1);
  364. for(i=0; i<num_transitions; i++){
  365. //printf("\nTRANSICAO: %d\n", i+1);
  366. if(arrayTransitions[i][0][estado] ==1){
  367. node *new_node = create_node(-1,sequencia_aux, 0,num_places);
  368. for(j = 0; j<num_places; j++){
  369. if(arrayTransitions[i][0][j] == 1){
  370. if(sequencia_aux[j] == 0){
  371. finalState = 1;
  372. }
  373. if(sequencia_aux[j]>0){
  374. sequencia_aux[j]-=1;
  375. }
  376. }
  377. }
  378. for(j = 0; j<num_places; j++){
  379. if(arrayTransitions[i][1][j]==1){
  380. //printf("\n--->adiciona no estado: %d\n", j+1);
  381. if(sequencia_aux[j] == -1){
  382. new_node->sequencia[j] = -1;
  383. new_node->estado[j] = 1;
  384. }else{
  385.  
  386. sequencia_aux[j]+=1;
  387. new_node->estado[j]=1;
  388. }
  389.  
  390. }else{
  391. if(sequencia_aux[j] == -1){
  392. new_node->estado[j] = -1;
  393. new_node->sequencia[j] = -1;
  394. }else{
  395.  
  396. new_node->estado[j] = -1;
  397. }
  398.  
  399. //sequencia_aux[j] = 0;
  400. }
  401. }
  402. memset(new_node->sequencia, 0, sizeof(new_node->sequencia));
  403. for(k=0; k<num_places; k++){
  404. new_node->sequencia[k] = sequencia_aux[k];
  405.  
  406. }
  407. new_node->transicao_come_from = i;
  408. new_node->father = father;
  409. add_son(father, new_node);
  410.  
  411. node * aux = new_node->father;
  412. node * aux2 = (node *)malloc(sizeof(node));
  413. aux2 = checkSequence(new_node, aux, num_places);
  414. printf("antes while\n");
  415. print_seq(aux->sequencia,num_places);
  416. while(aux !=NULL&&(aux2->transicao_come_from==-99)){
  417. aux = aux->father;
  418.  
  419. if(aux!=NULL){
  420. print_seq(aux->sequencia,num_places);
  421. aux2 = checkSequence(new_node, aux, num_places);
  422. printf("inside\n");
  423. print_seq(aux->sequencia,num_places);
  424. print_seq(aux2->sequencia,num_places);
  425. }
  426.  
  427. }
  428. printf("depois while\n");
  429. for(s = 0; s<num_places; s++){
  430. new_node->sequencia[i] = aux2->sequencia[i];
  431. }
  432.  
  433. printf("depois for\n");
  434. //printf("\nSEQ1: %d ; SEQ2: %d", root->sequencia[0], new_node->sequencia[0]);
  435. if(search_node(root, new_node, num_places) ==0){//0 nao encontra, 1 encontra
  436.  
  437. printf("dentro search do if\n");
  438. if(finalState == 1){
  439. done = 0;
  440. }else{
  441. done = 1;
  442. }
  443. printf("1-done: %d",done);
  444. return done;
  445. }else{
  446. done = 0;
  447. }
  448. printf("2-done: %d",done);
  449. return done;
  450. }
  451.  
  452. }
  453. memset(sequencia_aux, 0, sizeof(sequencia_aux));
  454. for(p = 0; p<num_places;p++){
  455. sequencia_aux[p] = father->sequencia[p];
  456. }
  457. }else{
  458. printf("3-done: %d",done);
  459. return done;
  460. }
  461. printf("4-done: %d",done);
  462. return done;
  463.  
  464. }
  465.  
  466. int get_estado(node* father, int num_places){
  467. int i=0;
  468. for(i=0; i<num_places; i++){
  469. if(father->estado[i] != 0 && father->estado[i] != -1){
  470. //printf("\nFATHER ESTADO: %d\n", i+1);
  471. father->estado[i] = -1;
  472. return i;
  473. }
  474. }
  475. return-1;
  476. }
  477.  
  478.  
  479. void add_son(node* father,node* new_son){
  480. int i;
  481. // printf("\n---add_son\n");
  482.  
  483. //printf("aqui: %d\n",new_son->estado);
  484.  
  485. if(father->son!=NULL){
  486. node* aux;
  487. //aux= (node *)malloc(sizeof(node));
  488. aux=father->son;
  489. // printf("ja tem pelo menos 1 filho\n");
  490. while(aux->brother!=NULL){
  491. //erro AQUIIIIIIIIIIIIIIIIII
  492. //printf("tem filho\n");
  493. aux=aux->brother;
  494. //printf("continuacao\n");
  495. }
  496. //printf("adiciona novo filho\n");
  497. aux->brother=new_son;
  498. aux=aux->brother;
  499. // printf("estado: %d",aux->estado);
  500. //
  501. // printf("seq:\n");
  502. // for(i=0;i<4;i++){
  503. // printf("%d ",aux->sequencia[i]);
  504. // }
  505.  
  506. //printf("\nsai add\n");
  507. }else{
  508. //printf("primeiro filho\n");
  509. father->son=new_son;
  510. }
  511. }
  512.  
  513. void print(node* root,int places){
  514. node* aux=root;
  515. node* aux2=root;
  516. int i;
  517. while(aux->sequencia[0]!=NULL){
  518. for(i=0;i<places;i++){
  519. printf("%d ",aux->sequencia[i]);
  520.  
  521. }
  522.  
  523. printf("\n");
  524. printf("estado: %d\n\n",aux->estado);
  525. if(aux->brother!=NULL){
  526. printf("vai para irmao \n");
  527. aux=aux->brother;
  528. }else{
  529. if(aux2->son!=NULL){
  530. aux=aux2->son;
  531. aux2=aux2->son;
  532. }else{
  533. break;
  534. }
  535.  
  536. }
  537. }
  538. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!