Fostering students' computer programming ability has been recognized as being an important and challenging educational issue which is highly related to the process of problem solving. However, most existing computer programming instruction mainly focuses on the training of programming language syntax and programming skills, while the problem-solving concepts are often ignored. Thus, in this study, an integrated Scratch and project-based learning approach is proposed to embed problem-solving scenarios in programming learning tasks. To test the effectiveness of the proposed approach, a total of 91 secondary school students, including 43 average students and 48 mathematics gifted students, participated in a project-based learning activity. The experimental results showed that the proposed learning approach could be fitted to all types of students. However, the mathematics gifted students outperformed the average students in terms of problem-solving performance, learning attitude and learning motivation. Furthermore, both average and mathematics gifted students showed significant progress after the learning activity, implying that the proposed approach benefited all of the students, no matter whether they tended to be gifted in mathematics or not.