\documentclass[11pt]{article} % Escrevendo em português \usepackage[brazil]{babel} \usepackage[latin1]{inputenc} %\language=1 \pagestyle{empty} \setlength{\topmargin}{-.5in} \setlength{\textheight}{9.7in} \setlength{\oddsidemargin}{-.125in} \setlength{\evensidemargin}{-.125in} \setlength{\textwidth}{6.75in} \newcommand{\sen}{\makebox[0.8cm]{sen}} \def\bk {$\backslash$} \newcommand{\comb}[2] %% to be used in math mode {\left( \begin{array}{c} #1 \\ #2 \end{array} \right) } \def\ua{\uparrow} \def\ni{\noindent} \def\pulo{\vspace{0.2cm}} \def\pulao{\vspace{0.5cm}} \def\pulaozao{\vspace{1cm}} \newcommand{\primeira}[1] {$#1^{\mbox{\scriptsize\b{a}}}$} \newcommand{\primeiro}[1] {#1$^{\mbox{\scriptsize\b{o}}}$} \pagestyle{empty} \begin{document} \begin{center} \large {\bf MAC 115 -- Introdução à Computação}\\\vspace{1\jot} {Instituto de Física -- Segundo Semestre de 2000 - Diurno} \pulao\\ Prova Substitutiva -- 15/12/2000 \end{center} \ni Nome do aluno: \underline{\makebox[9cm]{}} Turma:\underline{\makebox[2.7cm]{}} \pulao \\ Assinatura: \underline{\makebox[13.8cm]{}} \pulao \\ Professor(a): \underline{\makebox[13.6cm]{}} \pulao \\ \primeiro{N} USP: \underline{\makebox[7.2cm]{}} \hspace{0.2cm} Curso: \underline{\makebox[5.4cm]{}} \vspace{1.5cm} \ni {\bf Instruções:} \begin{enumerate} \item Não destaque as folhas deste caderno. \item A prova pode ser feita a lápis. Cuidado com a legibilidade. \item Há~$3$ questões na prova. Verifique antes de começar a prova se o seu caderno de questões está completo. \item Não é permitido o uso de folhas avulsas para rascunho. \item Nas questões que envolvem elaboração de programas, coloque comentários suficientes para que o programa seja facilmente compreendido. \item Não é necessário apagar rascunhos no caderno de questões, mas indique claramente onde estão suas respostas. \end{enumerate} \vspace{1.5cm} \begin{center} \large Não escreva nesta parte da folha \end{center} \ni \begin{center} \begin{tabular}{|c|c|} \hline \rule[-0.25cm]{0cm}{0.8cm}Quest\~ao & \makebox[2cm]{Nota} \\ \hline \hline \rule[-0.25cm]{0cm}{0.8cm}1 & \\ \hline \rule[-0.25cm]{0cm}{0.8cm}2 & \\ \hline \rule[-0.25cm]{0cm}{0.8cm}3 & \\ \hline %\rule[-0.25cm]{0cm}{0.8cm}4 & \\ \hline \hline \rule[-0.25cm]{0cm}{0.8cm}Total & \\ \hline \end{tabular} \end{center} \begin{center} \bigskip \textbf{BOA SORTE!} \bigskip \end{center} \newpage \ni{\underline {\bf Quest\~ao 1}}~~(valor: 3.0) \medskip \ni Simule a execução do programa abaixo \textit{destacando a sua saída} (o que vai sair na tela). Dados de entrada (a serem lidos): nenhum. {\small \begin{verbatim} #include #define TRUE 1 #define FALSE 0 int f1(int a, int b, int c); void f2(int a, int b, int *pmin, int *pmax); void f3(int v[], int n); /*------------------------------------------------*/ int main() { int x, y, z, w, a[4]; x = 4; y = 7; z = 5; printf("Funcao f1:\n"); printf("x = %d y = %d z = %d \n", x, y, z); printf("f1(%d, %d, %d) = %d \n\n", x, y, z, f1(x, y, z)); printf("Funcao f2:\n"); f2(x, y, &z, &w); printf("x = %d y = %d z = %d w = %d\n\n", x, y, z, w); printf("Funcao f3:\n"); a[0] = 3; a[1] = 7; a[2] = 1; a[3] = 5; printf(" a[0] = %d a[3] = %d\n", a[0], a[3]); f3(a, 4); printf(" a[0] = %d a[3] = %d\n\n", a[0], a[3]); return 0; } /*------------------------------------------------*/ int f1(int a, int b, int c) { if ((a + b + c) % 2 == 0) return TRUE; else return FALSE; } /*------------------------------------------------*/ void f2(int a, int b, int *pmin, int *pmax) { if (a > b) { *pmax = a; *pmin = b; } else { *pmax = b; *pmin = a; } printf("Dentro da funcao f2: maior = %d, menor = %d.\n", *pmax, *pmin); } \end{verbatim} } \newpage {\small \begin{verbatim} /*------------------------------------------------*/ void f3(int v[], int n) { int i, min, max; min = max = v[0]; for (i = 1; i < n; i++) { if (v[i] < min) min = v[i]; if (v[i] > max) max = v[i]; } v[0] = min; v[n - 1] = max; } \end{verbatim} } {\small \baselineskip=0.15cm \begin{verbatim} #====================================================================# # função f1 # função f2 # função f3 # #===========#========================#===============================# # a | b | c # a | b |*pmin |*pmax # v[0] v[1] v[2] v[3] min max n # #---|---|---#----|-----|------|------#-------------------------------# # | | # | | | # # # | | # | | | # # # | | # | | | # # # | | # | | | # # # | | # | | | # # #====================================================================# #========================# # função main() # #========================# # x | y | z | w # #-----|-----|-----|------# # | | | # # | | | # # | | | # # | | | # #========================# \end{verbatim} } {\small \begin{verbatim} Saída (o que vai sair na tela): ------------------------------- \end{verbatim} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage \noindent {\underline {\bf Quest\~ao 2}}~~(valor: 3.0) \medskip \ni Nesta questão, vamos representar inteiros (possivelmente com um número grande de dígitos) em vetores. Por exemplo, para representar o inteiro $$ \mathtt{31415926535897932384626433832795028841971693993751}, $$ armazenamos em um vetor, digamos \texttt{v[]}, os dígitos \texttt{1}, \texttt{5}, \texttt{7}, \texttt{3}, \texttt{9}, \texttt{9}, etc, nesta ordem, isto é, \texttt{v[0] = 1}, \texttt{v[1] = 5}, \texttt{v[2] = 7}, e assim por diante (é mais conveniente termos os dígitos na `ordem inversa'). A idéia é escrever um programa que soma dois inteiros (grandes) dados. Você deve supor que, nesta questão, os inteiros a serem somados têm no máximo \texttt{1000} dígitos. \begin{enumerate} \item [(\textit{a})] Escreva uma função de protótipo {\small \begin{verbatim} void leia_vetor(int v[], int n); \end{verbatim} } que lê as entradas de um vetor inteiro \texttt{v[]} de \texttt{n} elementos. Escreva também uma função de protótipo {\small \begin{verbatim} void imprima_vetor(int v[], int n); \end{verbatim} } que imprime o vetor inteiro~\texttt{v[]} de \texttt{n} elementos. Sua função \texttt{imprima\_vetor()} deve imprimir os elementos de \texttt{v[]} na ordem `reversa': primeiro \texttt{v[n-1]}, depois \texttt{v[n-2]}, etc, sem deixar espaço entre estes inteiros. \newpage \item [(\textit{b})] Escreva uma função de protótipo {\small \begin{verbatim} int some(int s[], int a[], int n_a, int b[], int n_b); \end{verbatim} } que recebe em \texttt{a[]} e, respectivamente, em \texttt{b[]} as seqüências de dígitos dos inteiro~$a$ e~$b$ (como explicado no início desta questão), e que devolve em \texttt{s[]} uma representação da soma $a+b$. A sua função deve receber em \texttt{n\_a} e em \texttt{n\_b} o número de dígitos de~$a$ e~$b$, respectivamente, e deve devolver o número de dígitos na soma~$a+b$. \begin{itemize} \item[]\textit{Exemplo}. Suponha que $a=82434256$ e~$b=33752337$. Então, a sua função será chamada com {\small \begin{verbatim} a = {6, 5, 2, 4, ... } b = {7, 3, 3, 2, ... } \end{verbatim} } e \texttt{n\_a = n\_b = 8}. A sua função deve então produzir o vetor {\small \begin{verbatim} s = {3, 9, 5, 6, ... } \end{verbatim} } pois $a+b=116186593$, e o valor devolvido por \texttt{some()} deve ser~$9$ ($a+b$ tem~$9$ dígitos). \end{itemize} \newpage \item [(\textit{c})] Escreva um programa que recebe dois inteiros positivos~$a$ e~$b$ com~$n_a$ e~$n_b$ dígitos, respectivamente, e determina a soma~$a+b$. Os valores de~$n_a$ e~$n_b$ são dados pelo usuário, e os números~$a$ e~$b$ são fornecidos dígito por dígito, na ordem reversa (unidades primeiro, depois dezenas, depois centenas, etc). \begin{itemize} \item[]\textit{Exemplo}. Suponha que $a=82434251$ e~$b=33752337$. Então, a entrada do seu programa será {\small \begin{verbatim} 8 1 5 2 4 3 4 2 8 8 7 3 3 2 5 7 3 3 \end{verbatim} } e a saída deve ser {\small \begin{verbatim} 82434251 + 33752337 = 116186588 \end{verbatim} } \end{itemize} \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage \ni{\underline{\bf Quest\~ao 3}}~~(valor: 4.0) \medskip \ni Dada uma matriz inteira, definimos o {\it peso\/} de uma linha dessa matriz como sendo a soma do {\it menor\/} e do {\it maior\/} elemento dessa linha. Por exemplo, na matriz $$ A=\pmatrix{ \hfill-4&\hfill7&\hfill8&\hfill10&\hfill-17&\hfill28 \cr \hfill2&\hfill3&\hfill-5&\hfill8&\hfill15&\hfill25 \cr \hfill-8&\hfill10&\hfill14&\hfill-16&\hfill20&\hfill48 \cr \hfill7&\hfill8&\hfill9&\hfill12&\hfill18&\hfill-45 }, $$ as linhas têm peso~$11$, $20$, $32$, e~$-17$. \medskip \begin{itemize} \item [(\textit{a})] Escreva uma função de protótipo {\small \begin{verbatim} void leia_matriz(int a[][NMAX], int m, int n); \end{verbatim} } que lê as entradas da matriz inteira \texttt{a} (\texttt{m x n}). Escreva também uma função de protótipo {\small \begin{verbatim} void imprima_matriz(int a[][NMAX], int m, int n); \end{verbatim} } que imprime a matriz inteira \texttt{a} (\texttt{m x n}). \newpage \item [{\rm(\textit{b})}] Escreva uma função de protótipo {\small \begin{verbatim} void menor_maior(int v[], int comp, int *pmin, int *pmax); \end{verbatim} } que recebe um vetor inteiro \texttt{v[]} e um inteiro \texttt{comp} (o número de elementos de \texttt{v[]}), e devolve o menor e o maior elemento do vetor \texttt{v[]} em \texttt{*pmin} e \texttt{*pmax}. \newpage \item [(\textit{c})] Escreva uma função de protótipo {\small \begin{verbatim} int processe_matriz(int a[][NMAX], int m, int n); \end{verbatim} } que recebe uma matriz inteira~\texttt{a} (\texttt{m x n}), e imprime o seguinte: \begin{itemize} \item o menor e o maior elemento de cada linha e o peso desta linha, \item o índice da linha de maior peso, \item o peso máximo encontrado. \end{itemize} (Em caso de haver mais de uma linha de peso máximo, \texttt{processe\_matriz()} deve imprimir o índice de qualquer uma delas.) Ao ser chamada com a matriz~$A$ acima, sua função deve imprimir algo como {\small \begin{verbatim} Pesos: 0: -17 28 peso = 11 1: -5 25 peso = 20 2: -16 48 peso = 32 3: -45 18 peso = -17 Linha de maior peso: 2 Peso maximo: 32 \end{verbatim} } Finalmente, \texttt{processe\_matriz()} deve devolver o índice da linha de maior peso ($2$, no exemplo acima). Você deve obrigatoriamente usar a função \texttt{menor\_maior()} acima, mesmo que você não a tenha feito. \newpage \item [{\rm(\textit{d})}] Escreva um programa que recebe como entrada dois inteiros $m$ e~$n$ (com $0 < m,\,n \leq 50$) e uma matriz inteira $A\; (m\times n)$, e que, primeiro, imprime a matriz lida. Uma vez impressa a matriz, o seu programa deve chamar função do item~(\textit{c}) para esta matriz. Seu programa deve ainda imprimir os elementos da linha de~$A$ com peso máximo. \begin{itemize} \item[]\textit{Exemplo}. Suponha que a entrada de seu programa é {\small \begin{verbatim} 4 6 -4 7 8 10 -17 28 2 3 -5 8 15 25 -8 10 14 -16 20 48 7 8 9 12 18 -45 \end{verbatim} } A saída de seu programa poderia então ser algo como {\small \begin{verbatim} Matriz lida: -4 7 8 10 -17 28 2 3 -5 8 15 25 -8 10 14 -16 20 48 7 8 9 12 18 -45 Pesos: 0: -17 28 peso = 11 1: -5 25 peso = 20 2: -16 48 peso = 32 3: -45 18 peso = -27 Linha de maior peso: 2 Peso maximo: 32 Elementos da linha de peso maximo: -8 10 14 -16 20 48 \end{verbatim} } \end{itemize} \end{itemize} \end{document}