{"id":1342,"date":"2022-07-04T15:51:34","date_gmt":"2022-07-04T18:51:34","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/programacao\/?p=1342"},"modified":"2022-07-04T15:51:37","modified_gmt":"2022-07-04T18:51:37","slug":"exercicio-resolvido-otimizando-solucoes","status":"publish","type":"post","link":"http:\/\/www.galirows.com.br\/meublog\/programacao\/exercicio-resolvido-otimizando-solucoes\/","title":{"rendered":"Exerc\u00edcio resolvido – otimizando solu\u00e7\u00f5es"},"content":{"rendered":"\n

Inicio com um exerc\u00edcio de algoritmos bastante tradicional e simples. O exerc\u00edcio consiste em determinar se um n\u00famero \u00e9 par ou \u00edmpar. <\/p>\n\n\n\n

Para resolver, o algoritmo abaixo foi o primeiro que desenvolvi e possivelmente \u00e9 a solu\u00e7\u00e3o que seria, de maneira similar, desenvolvida pela maioria das pessoas. Na solu\u00e7\u00e3o \u00e9 testado se o valor resultante da sobra da divis\u00e3o do n\u00famero por dois \u00e9 igual a zero, ou seja, verificado se o n\u00famero \u00e9 divis\u00edvel por 2.<\/p>\n\n\n\n

#include <stdio.h>\n\nint main() {\n    int x = 18;\n\n    if (x%2 == 1) {\n        printf(\"Impar\");\n    } else {\n        printf(\"Par\");\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
Uma forma otimizada para resolver esse problema \u00e9 utilizar o operador bitwise AND<\/em>. O c\u00f3digo a seguir mostra a solu\u00e7\u00e3o utilizando esse operador e \u00e9 bastante parecido com o anterior, apenas alterando a condi\u00e7\u00e3o de teste na linha 6.<\/p>\n\n\n\n
A solu\u00e7\u00e3o utilizando o bitwise<\/em> uma solu\u00e7\u00e3o mais sofisticada, mas mais eficiente. Logicamente \u00e9 necess\u00e1rio entender sobre o operador bitwise AND<\/em>, o que pode ser visto em http:\/\/www.galirows.com.br\/meublog\/programacao\/operadores-bitwise-cpp\/<\/a>. Como em bin\u00e1rios, o n\u00famero 1 = 00000001, e operador somente resulta em 1 se dos dois bits comparados forem o valor 1, somente um n\u00famero com o \u00faltimo bit 1 \u00e9 que resultaria o teste em verdadeiro e com isso sabemos que o n\u00famero \u00e9 \u00edmpar.<\/p>\n\n\n\n
#include <stdio.h>\n\nint main() {\n    int x = 18;\n\n    if (x & 1) {\n        printf(\"Impar\");\n    } else {\n        printf(\"Par\");\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
Claramente a solu\u00e7\u00e3o utiliza um conhecimento adicional da linguagem C com a manipula\u00e7\u00e3o de bits, mas de que maneira isso torna a solu\u00e7\u00e3o mais eficiente? a opera\u00e7\u00e3o com bits costuma ser mais r\u00e1pida do que as opera\u00e7\u00f5es aritm\u00e9ticas e relacionais. A diferen\u00e7a \u00e9 bem pequena e para testar \u00e9 preciso realizar as opera\u00e7\u00f5es muitas vezes. No c\u00f3digo abaixo os c\u00e1lculos s\u00e3o feitos v\u00e1rias vezes. Utilizando o c\u00e1lculo da linha 6 do c\u00f3digo abaixo o tempo m\u00e9dio das execu\u00e7\u00f5es que executei ficaram em torno de 4,6 segundos, enquanto utilizando o c\u00e1lculo da linha 5 o tempo foi de 4,7 segundos. <\/p>\n\n\n\n
\u00c9 pouca diferen\u00e7a? sim. Ainda mais considerando que a opera\u00e7\u00e3o dificilmente seria realizada tantas vezes em uma solu\u00e7\u00e3o. Ent\u00e3o n\u00e3o existe problema algum em utilizar a solu\u00e7\u00e3o tradicional, mas \u00e9 interessante conhecer a alternativa com o bitwise<\/em>.<\/p>\n\n\n\n
#include <stdio.h>\n\nint main() {\n    for (int i=0; i < 2147483647; i++)\n        (i % 2 == 1);\n        \/\/(i & 1);\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
Veja que solicitei para o la\u00e7o for<\/em> executar 2.147.483.647 vezes e que esse \u00e9 o valor m\u00e1ximo que uma vari\u00e1vel int<\/em> pode assumir.<\/p>\n\n\n\n
\n\n\n\n
Dado um conjunto de n\u00fameros onde todos os elementos ocorrem um n\u00famero par de vezes, exceto um desses valores, encontre o n\u00famero que ocorre um n\u00famero \u00edmpar de vezes.<\/p>\n\n\n\n
Para resolver, o algoritmo abaixo foi o primeiro que desenvolvi. Na fun\u00e7\u00e3o principal \u00e9 criado o vetor com alguns valores e chamada a fun\u00e7\u00e3o acharImpar()<\/em>. Essa fun\u00e7\u00e3o cria uma matriz com duas colunas na qual em cada linha ser\u00e3o armazenados cada valor encontrado do vetor e na coluna correspondente o n\u00famero de vezes que o valor foi encontrado. O n\u00famero de linhas da matriz considerou o maior tamanho dessa matriz: se todos os valores formarem um par + um n\u00famero sem par. No caso do meu vetor definido na fun\u00e7\u00e3o main()<\/em>, a matriz ter\u00e1 9\/2+1=5 linhas (lembre-se que 9\/2=4, uma vez que int\/int<\/em> resulta apenas na parte inteira da divis\u00e3o), embora apenas 4 ser\u00e3o realmente utilizadas.<\/p>\n\n\n\n
O algoritmo se baseia em adicionar na matriz cada novo n\u00famero encontrado no vetor e contar quantas vezes cada um deles ocorre. Ao final \u00e9 buscado qual das contagens de ocorr\u00eancia resulta em um valor \u00edmpar e o valor correspondente \u00e9 retornado.<\/p>\n\n\n\n
#include <stdio.h>\n\nint acharImpar(int arr[], int n) {\n    int i, j, qtd=0, mat[n\/2+1][2];\n\n    for (i=0; i < n; i++) {\n        \/\/verifica se o valor j\u00e1 est\u00e1 na matriz\n        for (j=0; j < qtd; j++) {\n            if (mat[j][0] == arr[i]) {\n                mat[j][1]++;\n                j = n;\n                break;\n            }\n        }\n        \/\/adiciona novo valor na matriz\n        if (j != n) {\n            mat[qtd][0] = arr[i];\n            mat[qtd][1] = 1;\n            qtd++;\n        }\n    }\n\n    \/\/mostra a matriz\n    for (i=0; i < qtd; i++) {\n        printf(\"%i: %i \\n\", mat[i][0], mat[i][1]);\n    }\n\n    \/\/retorna a ocorr\u00eancia \u00edmpar\n    for (i=0; i < qtd; i++) {\n        if (mat[i][1]%2 == 1) {\n            return mat[i][0];\n        }\n    }\n}\n\nint main(void) {\n    int arr[] = { 10, 10, 11, 11, 11, 20, 12, 11, 12 };\n    int n = sizeof(arr) \/ sizeof(arr[0]); \/\/calcula o tamanho do vetor\n    printf(\"O valor que aparece um numero impar de vezes eh: %d \", acharImpar(arr, n));\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
Agora apresento uma solu\u00e7\u00e3o que utiliza uma opera\u00e7\u00e3o bitwise<\/em>. O c\u00f3digo abaixo para a fun\u00e7\u00e3o acharImpar()<\/em> utiliza o bitwise XOR<\/em> e obt\u00e9m o mesmo resultado da vers\u00e3o anterior. \u00c9 uma solu\u00e7\u00e3o mais sofisticada com certeza, mas mais econ\u00f4mica na aloca\u00e7\u00e3o de mem\u00f3ria pois dispensa a utiliza\u00e7\u00e3o da matriz. <\/p>\n\n\n\n
int acharImpar(int arr[], int n) {\n    int res = 0, i;\n    for (i = 0; i < n; i++)\n        res ^= arr[i];\n        \/\/printf(\"%d: %d \\n\", arr[i], res);\n    return res;\n}<\/code><\/pre>\n\n\n\n
Para entender o que ocorre nesse c\u00f3digo, considere o que seria mostrado com o printf <\/em>da linha 5. O resultado \u00e9 mostrado abaixo. Veja que a cada intera\u00e7\u00e3o ocorrer uma soma e depois uma subtra\u00e7\u00e3o do valor do array. Assim, cada par de valor acaba se anulando, mesmo que n\u00e3o estejam consecutivamente, e fica sobrando apenas o valor que n\u00e3o tinha um par.<\/p>\n\n\n\n
10: 10\n10: 0\n11: 11\n11: 0\n11: 11\n20: 31\n12: 19\n11: 24\n12: 20<\/code><\/pre>\n\n\n\n
Veja que nessa solu\u00e7\u00e3o foi utilizado o princ\u00edpio do operador XOR, que funciona identificando um elemento que ocorre exclusivamente.<\/p>\n\n\n\n
Espero ter ajudado a entender um pouco mais sobre os operadores bitwise<\/em>. At\u00e9 uma pr\u00f3xima.<\/p>\n","protected":false},"excerpt":{"rendered":"
Inicio com um exerc\u00edcio de algoritmos bastante tradicional e simples. O exerc\u00edcio consiste em determinar se um n\u00famero \u00e9 par ou \u00edmpar. Para resolver, o algoritmo abaixo foi o primeiro que desenvolvi e possivelmente \u00e9 a solu\u00e7\u00e3o que seria, de maneira similar, desenvolvida pela maioria das pessoas. Na solu\u00e7\u00e3o \u00e9 testado se o valor resultante […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[3,58],"tags":[],"class_list":["post-1342","post","type-post","status-publish","format-standard","hentry","category-c","category-codigo-com-analise"],"aioseo_notices":[],"amp_enabled":true,"_links":{"self":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/1342","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/comments?post=1342"}],"version-history":[{"count":5,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/1342\/revisions"}],"predecessor-version":[{"id":1360,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/posts\/1342\/revisions\/1360"}],"wp:attachment":[{"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/media?parent=1342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/categories?post=1342"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/programacao\/wp-json\/wp\/v2\/tags?post=1342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}