[C language algorithm] Block movement

Implemented block movement algorithm in C language

Environment used for learning

Reference material

Latest algorithm dictionary in C language (written by Haruhiko Okumura / 1991 first edition Gijutsu-Hyoronsha: 249 pages)

Overview of block movement algorithm

It is an algorithm that replaces blocks in a character string.

(The following is quoted from the reference material)

If you move block 12345 after block abcd in an editor instruction, eg text xyz12345abcdefg, you get xyzabcd12345efg. This operation is also to swap 12345 and abcd, or to rotate 12345abcd to the right by 4 characters.

This time, we implemented the process to change the character string "PROGRAMMING PRINCIPLES" consisting of two words "PROGRAMMING" and "PRINCIPLES" into "PRINCIPLES PROGRAMMING" by exchanging the words.

Source code

moveblock.c


/*Block move block move*/

#include <stdio.h>
#include <stdlib.h>

char sentense[] = "PROGRAMMINGPRINCIPLES";

int main(void) {
	printf("%s\n",sentense);
	//Call the string move function
	rotate(0, 10, 20);	
	printf("%s\n", sentense);

	return EXIT_SUCCESS;
}

//String inversion function
//If the string length is odd, only the center character is not inverted
void reverse(int i,int j){
	//Tmp variable to replace
	int t;
	while(i < j){
		t = sentense[i];
		sentense[i] = sentense[j];
		sentense[j] = t;
		
		//Shift the position of the character string to be processed one by one
		i++;
		j--;
		
		printf("%s i=%d j=%d (reverse)\n", sentense, i, j);
	}
}

//String movement function
//Call the reverse function
//First argument: Start position of the left part of the character string to be replaced
//Second argument: Start position of the right part of the character string to be replaced
//Third argument: The entire character string to be replaced
void rotate(int left, int mid, int right){
	reverse(left, mid);
	reverse(mid + 1,right);
	reverse(left, right);
}

Execution result

The result was as expected.

result.txt(Any)


Success #stdin #stdout 0s 4488KB

PROGRAMMINGPRINCIPLES
GROGRAMMINPPRINCIPLES i=1 j=9 (reverse)
GNOGRAMMIRPPRINCIPLES i=2 j=8 (reverse)
GNIGRAMMORPPRINCIPLES i=3 j=7 (reverse)
GNIMRAMGORPPRINCIPLES i=4 j=6 (reverse)
GNIMMARGORPPRINCIPLES i=5 j=5 (reverse)
GNIMMARGORPSRINCIPLEP i=12 j=19 (reverse)
GNIMMARGORPSEINCIPLRP i=13 j=18 (reverse)
GNIMMARGORPSELNCIPIRP i=14 j=17 (reverse)
GNIMMARGORPSELPCINIRP i=15 j=16 (reverse)
GNIMMARGORPSELPICNIRP i=16 j=15 (reverse)
PNIMMARGORPSELPICNIRG i=1 j=19 (reverse)
PRIMMARGORPSELPICNING i=2 j=18 (reverse)
PRIMMARGORPSELPICNING i=3 j=17 (reverse)
PRINMARGORPSELPICMING i=4 j=16 (reverse)
PRINCARGORPSELPIMMING i=5 j=15 (reverse)
PRINCIRGORPSELPAMMING i=6 j=14 (reverse)
PRINCIPGORPSELRAMMING i=7 j=13 (reverse)
PRINCIPLORPSEGRAMMING i=8 j=12 (reverse)
PRINCIPLERPSOGRAMMING i=9 j=11 (reverse)
PRINCIPLESPROGRAMMING i=10 j=10 (reverse)
PRINCIPLESPROGRAMMING

Impressions

Recommended Posts

[C language algorithm] Block movement
[C language algorithm] Endianness
[C language algorithm] Binary search tree
[C language algorithm] Postfix notation (or reverse Polish notation)
C language ALDS1_3_B Queue
Machine language embedding in C language
C language ALDS1_4_B Binary Search
Heapsort made in C language
[C language] readdir () vs readdir_r ()
C language ALDS1_4_A Linear Search
Multi-instance module test in C language
Function pointer and objdump ~ C language ~
Realize interface class in C language
Writing C language with Sympy (metaprogramming)
High energy efficiency programming language C
Introduction to Protobuf-c (C language ⇔ Python)
[Language processing 100 knocks 2020] Chapter 1: Preparatory movement
100 Language Processing Knock: Chapter 1 Preparatory Movement
100 Language Processing Knock 2020 Chapter 1: Preparatory Movement
C language 8 queens problem solving 3 patterns
Segfault with 16 characters in C language
Call c language from python (python.h)