The replica-exchange multicanonical algorithm and the multicanonical replica-exchange method for molecular dynamics simulations have recently been developed. In the former method the multicanonical weight factor is determined from a short replica-exchange simulation with the multiple-histogram reweighting techniques. A long multicanonical production run with high statistics is then performed with this weight factor. In this method, the process of determining the multicanonical weight factor is faster and simpler than that in the usual iterative determination. The multicanonical replica-exchange method is a further extension of the first in which a replica-exchange multicanonical simulation is performed with a small number of replicas. In this paper, we give the formulations of these two methods for Monte Carlo simulations and demonstrate the effectiveness of these algorithms for a penta peptide in the gas phase. (C) 2003 American Institute of Physics.