Search the Community

Boas, pessoal! Estou a tentar aprofundar o meu conhecimento em algoritmia e cruzei-me com o famoso problema LCS. Implementei uma solução que recorre a uma adaptação do Algoritmo de Wagner-Fischer para determinar qual o comprimento da maior substring comum. Contudo, a complexidade é O(m.n), o que no pior caso se traduz em O(n²). Após pesquisa, encontrei referências à possível existência de algoritmos com melhor complexidade. Venho, pois, ter convosco para vos lançar o tópico, debater algoritmos e saciar a minha curiosidade: conheceis algoritmos com melhor complexidade para resolver este problema? Se sim, quais e com que complexidade? Obrigado desde já. Cumprimentos.

Sou iniciante em Java e estou tendo dificuldades para executar o algoritmo Stable Marrage de GaleShapley,. Na execução aparece o seguinte erro: Error: Index 3 out of bounds for length 3 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 3 at br.com.entrada.GaleShapley.calcMatches(GaleShapley.java:48) at br.com.entrada.GaleShapley.<init>(GaleShapley.java:33) at br.com.entrada.GaleShapley1.main(GaleShapley1.java:164) Gale Shapley Marriage Algorithm Sized : 3 Segue o código abaixo: import java.io.BufferedReader; import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; public class GaleShapley { private int N, engagedCount; private String[][] menPref; private String[][] womenPref; private String[] men; private String[] women; private String[] womenPartner; private boolean[] menEngaged; /** Constructor **/ public GaleShapley (){ } public GaleShapley(String[] m, String[] w, String[][] mp, String[][] wp) { System.out.println("Sized : "+ mp.length); N = mp.length; engagedCount = 0; men = m; women = w; menPref = mp; womenPref = wp; menEngaged = new boolean[N]; womenPartner = new String[N]; calcMatches(); } /** function to calculate all matches **/ private void calcMatches() { while (engagedCount < N) { int free; for (free = 0; free < N; free++) if (!menEngaged[free]) break; for (int i = 0; i < N && !menEngaged[free]; i++) { int index = womenIndexOf(menPref[free]); if (index < womenPartner.length && womenPartner[index] != null ) { womenPartner[index] = men[free]; menEngaged[free] = true; engagedCount++; } else { String currentPartner = womenPartner[index]; if (morePreference(currentPartner, men[free], index)) { womenPartner[index] = men[free]; menEngaged[free] = true; menEngaged[menIndexOf(currentPartner)] = false; } } } } printCouples(); } /** function to check if women prefers new partner over old assigned partner **/ private boolean morePreference(String curPartner, String newPartner, int index) { for (int i = 0; i < N; i++) { if (womenPref[index].equals(newPartner)) return true; if (womenPref[index].equals(curPartner)) return false; } return false; } /** get men index **/ private int menIndexOf(String str) { for (int i = 0; i < N; i++) if (men.equals(str)) return i; return -1; } /** get women index **/ private int womenIndexOf(String str) { for (int i = 0; i < N; i++) if (women.contains(str)) return i; return -1; } /** print couples **/ public void printCouples() { System.out.println("Couples are : "); for (int i = 0; i < N; i++) { System.out.println(womenPartner +" "+ women); } } /** main function **/ public static void main(String[] args) throws IOException{ System.out.println("Gale Shapley Marriage Algorithm\n"); /** list of men **/ String[] m = {"1", "2", "3"}; /** list of women **/ String[] w = {"1", "2", "3"}; /** men preference **/ String[][] mp = null ; /** women preference **/ String[][] wp= null ; try{ FileInputStream fstream = new FileInputStream("src/input.txt"); DataInputStream in = new DataInputStream(fstream); BufferedReader br = new BufferedReader(new InputStreamReader(in)); String strLine; int line=0; int k=0; int n=0; int i=0; while ((strLine = br.readLine()) != null) { if(line==0){ n =Integer.valueOf(strLine.trim()); mp=new String[n][n]; wp=new String[n][n]; line++; } else{ String[] preferences=strLine.split(" "); if(i<n){ mp=preferences; } else{ if(i-n < w.length) { wp[i-n]=preferences; } } i++; } } in.close(); GaleShapley gs = new GaleShapley(m, w, mp, wp); }catch (Exception e){//Catch exception if any e.printStackTrace(); System.err.println("Error: " + e.getMessage()); } } }

Olá, Eu sou novo aqui, e na area de ''programação'', queria perguntar se alguém que conseguiria ajudar com alguns exercíos que tenho tido dificuldade em resolver. Exercício 1:Escrever em pseudocódigo um programa que some os três primeiros múltiplos de 3 introduzidos pelo utilizador e que mostre o resultado da sua soma. Exercício 2:Modifique o algoritmo2 de forma a este mostrar uma mensagem de erro ao utilizador sempre que o número de segundos seja inferior a zero ou superior a 1000000. Sempre que isto se verifique não deverá efetuar qualquer processamento/cálculo. (Algoritmo: Determinar se um número é impar.) Exercício 3:Como alteraria o algoritmo3 de forma a este somar apenas os números ímpares, e a contagem iniciar com o valor 0, ao invés de 100, de forma a efetuar a mesma contagem, mas no sentido inverso. (Algoritmo:Imprimir números no intervalo de 1 a 100) Obrigado Cumprimentos e resto de Boa noite

Olá a todos, inicio este tópico porque preciso de ajuda sobre qual o algoritmo que é usado para calcular o digito de verificação (nono digito) do número de utente do SNS. Segundo a legislação (Portaria nº 981/95) link: https://dre.pt/web/guest/pesquisa/-/search/477871/details/normal?q=981%2F95 usa a Norma ISO 7064 (MOD 11-2). Pelas minhas pesquisas, e resumindo o algoritmo, o mod 11, multiplica : 1 2 3 4 5 6 7 8 9 ---- numero ficticio do SNS por 9 8 7 6 5 4 3 2 - ----- factor de multiplicação depois soma tudo e divide por 11 (Mod11), com base no resto da divisão faz 11-resto e o numero será o digito de verificação (sendo que se for 11 ou 10 aplica-se 0 Isto aplicado ao NIF funciona bem. Mas para o numero do SNS não. Alguém aqui no fórum me pode ajudar com isto?

olá pessoal, estou estudando programação há três meses, mais estou com alguns problemas. Preciso criar um algoritmo que calcule o século em que um ano se encontra. Já pesquisei mais ñ encontrei nada que possa me ajudar. Gostaria de saber como vocês (os mais experientes) resolveriam esse problema. desde já agradeço.

Olá a todos. Sou ex-participante em Portugal e agora estou a fazer doutouramento na Bélgica. Sou treinador das equipas para o NWERC e já por mais de 3 anos ganhamos medalhas. Este ano vamos organisar um campo de treino aqui na Bélgica: https://sites.uclouvain.be/acm-icpc18/index.html

Boa noite galera, estou estudando sobre pseudocodigos, recentemente e me surgiram exercicios nos quais tive problemas; programa calc var n,conta:inteiro inicio n <- 8 conta <- 2 repita conta <- conta + ( n – 1 ) n <- n – 1 até que n = 0 escreva conta fim. var x : inteiro inicio x <- 11 se ( x < > 1 0) se ( ( x > 15 ) OU ( x <= 20 ) ) x <- x + 2 senão x <- x – 4 fim_se fim_se se ( x MOD 4 >= 2 ) x <- x + 5 senão x <- x – 3 fim_se escreva “ x = “, x fim Conseguem me ajudar/explicar qual seria o resultado final de ambos os códigos?

Considerar a seguinte função em C#: public static bool DoThings(int[] x, int j, out int i) { i = 0; for (int i = 1; i < x.length(); ++i) if (x == j) ++i return i > 0; } Corrija a função de modo a que funcione (tenha um comportamento útil). Descreva o funcionamento implementado (para que serve a função).

Olá pessoal, estou precisando da vossa ajuda para resolver o seguinte problema: Considere a necessidade de representar uma data (dia, mês, ano). Defina uma classe que permita: definir uma nova data; Garantir que a data é válida (número de dias válido para o mês em causa, e mês válido); Funcione corretamente para anos bissextos. Um ano é bissexto se: ano % 4 == 0 && (ano % 100 != 0 || ano % 400 == 0) Permita o uso de propriedades para alterar dia, mês e ano (e obter respetivos valores); Implemente um método para a sua representação numa string devidamente formatada, Não é permitido a utilização da class DateTime.

Considere o cálculo da media de quatro algarismos. Apresente: a) O algoritmo simples em Fluxograma; b) O algoritmo simples em Pseudo-código;

Boa tarde, estou com um problema no desenvolvimento de um algoritmo e agradecia a vossa ajuda, caso seja possivel. Tenho um grupo de 20 pessoas, que respondem a um questionario de escolhas multiplas e a funçao do algoritmo é fazer a comparaçao entre todos os questionarios e devolver as que têm as respostas iguais. Alguem que consegue ajudar? Obrigado

Olá pessoal, será que me podem ajudar com um problema? Tenho de escrever o algoritmo disto: O seno de x pode ser calculado usando o desenvolvimento em série de Taylor Escreva e teste uma funçao que determine o seno de um angulo x (introduzido pelo utilizador em radianos), usando este desenvolvimento em série, até um termo em que a diferença para o termo seguinte tenha um valor absoluto abaixo de uma tolerância (especificada pelo utilizador). Sugestão: utilize uma funçao para calcular o fatorial de um número. P.S.: se vos der mais jeito podem fazer o programa e eu tento fazer o algoritmo a partir daí

Ordenador QuickSort com Threads Ver Ficheiro Implementação de ordenação usando multi-threading. Submetido por crislanio_macedo Submetido em 14-06-2015 Categoria Bibliotecas e Aplicações Licença Website https://github.com/crislanio/OrdenadorQuickSortComThreads Submetido pelo Autor? Sim

Boas eu tenho uma tabela hash polinomial, que me codifica palavras que têm 2 letras e 2 números. Por exemplo o formato que uso para a codificação é esta Onde k1 é a primeira letra, k2 a segunda ... e A é um número primo, que no meu caso é 11. Agora eu tenho a tabela com as palavras, sem qualquer problema a pesquisar palavras completas... O meu problema é, eu quero fazer uma função, onde é fornecida a primeira letra, e eu quero que ele me retorne todas as palavras na tabela que começam com essa letra. Não conhecendo a ordem da tabela visto que a hash gera as posições aleatóriamente, como é que posso fazer isto, sem ter que correr a tabela toda de ponta a ponta?

Boas pessoal... Sou novato aqui no forum e no mundo da programação. Estou com um sério problema e não sei como começar! Portanto, pretendia implementar o algoritmo Ricart-Agrawala em Java, usando JGroup como mecanismo de comunicação, devendo o sistema ser constituído apenas por um módulo (ou peer). Cumps

amigos preciso criar uma calculado em binário com as 4 operações básicas, em c++ e apresentar o algorítimo alguem me da alguma dica por favor

Bom dia, Estou a fazer o jogo do par ou impar no Python, e queria que o computador escolhe-se aleatoriamente se quer par ou impar para jogar. Para o computador gerar um numero aleatório para jogar utilizei a função random.randint, e agora queria que o computador escolha se quer ficar com o par ou com o impar. Mas não estou a conseguir fazer, alguém me consegue ajudar sff? Obrigado