We have developed a semi-analytic method of calculating the changes in heliocentric Keplerian orbital elements due to gravitational scattering by a protoplanet as a three-body problem. In encounters with high incident velocities, either the gravity of the protoplanet or the solar gravity can be regarded as perturbation force. In close encounters, by taking into account the solar gravity as a perturbation, we modified the two-body gravitational scattering. On the other hand, in slightly distant encounters, we apply the perturbing force of the protoplanet to the heliocentric Keplerian orbit of planetesimals. As a result, as for high-velocity encounters, the three-body problem is semi-analytically solvable. Our semi-analytic method can reproduce the numerical result of the orbital changes of individual planetesimals for the broad range of high-energy encounters with surprising high accuracy. We found that our method is valid under the conditions (i) b0 ≳ 2 and (ii) (e20 + i20 - 3/4 b20)1/2 ≳ 4, where e0 and i0 are eccentricity and inclination of relative motion normalized by the reduced Hill radius and b0 is the difference between semimajor axes normalized by the Hill radius. Though our method needs some numerical procedure, its cpu time is negligibly short compared with that of the direct orbital integration. In simulation of orbital evolution of planetesimals around a protoplanet in the gas, which we will perform in the subsequent paper, most encounters can be calculated by the semi-analytic method. This makes it possible to perform the long term (≃105 years) orbital calculation of ≃103-4 planetesimals.